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)?

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

Snowbody · Accepted Answer · 2014-07-02 20:16:55Z

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.

NotPro · Answer 2 · 2014-06-27 11:59:29Z

up vote 0 down vote

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(); 
}

answered Jun 27 at 11:59

NotPro
4964

1

@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. – svick Jun 28 at 14:26

@svick Yikes! I committed the cardinal sin of C#, assuming that it worked the same as C++. Thanks for setting me straight. – Snowbody Jun 30 at 19:48

1

@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>. – svick Jun 30 at 19:57

add comment

tinstaafl · Answer 3 · 2014-07-01 03:53:15Z

up vote 0 down vote

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!");
}

answered Jul 1 at 3:53

tinstaafl
1,695112

using Microsoft.VisualBasic in a C# project? o.O – Mat's Mug Jul 1 at 4:36

add comment

asked	27 days ago
viewed	116 times
active	21 days ago

current community

your communities

more stack exchange communities

Compare string with wildcard string

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged c# strings array loop or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Compare string with wildcard string

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# strings array loop or ask your own question.

Related

Hot Network Questions