Compare string with wildcard string

Question

I have the following function to compare a string with a wildcard string (containing ? and *), as C# doesn't seem to have a builtin function to do it.

 /// <summary>
 /// Compares wildcard to string
 /// </summary>
 /// <param name="WildString">String to compare</param>
 /// <param name="Mask">Wildcard mask (ex: *.jpg)</param>
 /// <returns>True if match found</returns>
 public static bool CompareWildcard(string WildString, string Mask, bool IgnoreCase = true)
 {
 int i = 0, k = 0;
 // Cannot continue with Mask empty
 if (string.IsNullOrEmpty(Mask))
 return false;
 // If WildString is null -> make it an empty string
 if (WildString == null)
 WildString = string.Empty;
 // If Mask is * and WildString isn't empty -> return true
 if (string.Compare(Mask, "*") == 0 && !string.IsNullOrEmpty(WildString))
 return true;
 // If Mask is ? and WildString length is 1 -> return true
 if (string.Compare(Mask, "?") == 0 && WildString.Length == 1)
 return true;
 // If WildString and Mask match -> no need to go any further
 if (string.Compare(WildString, Mask, IgnoreCase) == 0)
 return true;
 while (k != WildString.Length)
 {
 switch (Mask[i])
 {
 case '*':
 if ((i + 1) == Mask.Length)
 return true;
 while (k != WildString.Length)
 {
 if (CompareWildcard(WildString.Substring(k + 1), Mask.Substring(i + 1), IgnoreCase))
 return true;
 k += 1;
 }
 return false;
 case '?':
 break;
 default:
 if (IgnoreCase == false && WildString[k] != Mask[i])
 return false;
 if (IgnoreCase && Char.ToLower(WildString[k]) != Char.ToLower(Mask[i]))
 return false;
 break;
 }
 i += 1;
 k += 1;
 }
 if (k == WildString.Length)
 {
 if (i == Mask.Length || Mask[i] == '*')
 return true;
 }
 return false;
 }

I added the check to make sure Mask isn't null/empty because if it is then switch (Mask[i]) will throw a IndexOutOfRangeException. I'm wondering if there are any other checks I should make or change (specifically during the while loop)?

• Sleiman Jneidi: why dont you use Regex and you save yourself this hassle codeproject.com/Articles/11556/Converting-Wildcards-to-Regexes
• SameOldNick: @SleimanJneidi I want a foolproof method rather then something that has unknown problems with it
• Snowbody: Why do you think that the $Regex$ method "has unknown problems"? What would satisfy you that any solution was "foolproof"?

Answer 1

What you want to do is called "globbing". It's actually quite easy to do with a Regex.

There are a few code smells here. The recursion is the obvious one. The other is the special-cases. When you special-case the single-character wildcard, it suggests that you're thinking about the problem wrong. There's no reason why they would need to -- or even should -- be specialcased.

If you really want to reinvent the wheel, the "right way" is to build a state machine (削除) and backtrack (削除ここまで). I combined @NotPro's answer and @svick's hint to get http://ideone.com/VUDFIw but that uses backtracking. Check out http://swtch.com/~rsc/regexp/regexp1.html to see why backtracking is a bad idea, and how we can get an O(n) state machine.

Answer 2

Another option, as outlined in this blog is to not re-invent the wheel and use the VB.net LikeString method:

Add a reference to Microsoft.VisualBasic first.

using Microsoft.VisualBasic;
using Microsoft.VisualBasic.CompilerServices;
if(Operators.LikeString("This is just a test", "*just*", CompareMethod.Text))
{
 Console.WriteLine("This matched!");
}

• Mathieu Guindon: using Microsoft.VisualBasic in a C# project? o.O

Answer 3

You still have bug for wildString = "xyzz", mask = "?" .

The best idea is to use Regex but if you want implement your own solution I would use Linq. I think it's make solution much shorter and easier to understand.

static bool CompareWildcard(IEnumerable<char> input, string mask)
{
 for (int i = 0; i < mask.Length; i++)
 {
 switch (mask[i])
 {
 case '?':
 if (!input.Any())
 return false;
 input = input.Skip(1);
 break;
 case '*':
 while (input.Any() && !CompareWildcard(input, mask.Substring(i + 1)))
 input = input.Skip(1);
 break;
 default:
 if (!input.Any() || input.First() != mask[i])
 return false;
 input = input.Skip(1);
 break;
 }
 }
 return ! input.Any(); 
}

• svick: @Snowbody You're right that using Skip() this way is a bad idea (it leads to \$\mathcal{O}(n^2)\$ code), but how exactly do you clone Enumerator? A better way to do this might be to use ImmutableStack or FSharpList.
• Snowbody: @svick Yikes! I committed the cardinal sin of C#, assuming that it worked the same as C++. Thanks for setting me straight.
• svick: @Snowbody Now that I think about it, if input was string, then its enumerator is CharEnumerator, which can be cloned. But you can't do that with a general IEnumerator<char>.