Wildcard Matching

Problem: Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Approach: Use DP

        public bool IsWildCardMatch(string s, string p)

        {

            bool[,] lookup = new bool[s.Length + 1, p.Length + 1];

            lookup[0, 0] = true;

            for (int i = 1; i <= p.Length; ++i)

            {

                if (p[i - 1] == '*')

                {

                    lookup[0, i] = lookup[0, i - 1];

                }

            }

            for (int i = 1; i <= s.Length; ++i)

            {

                for (int j = 1; j <= p.Length; ++j)

                {

                    if (p[j - 1] == '*')

                    {

                        lookup[i, j] = lookup[i, j - 1] || lookup[i - 1, j];

                    }

                    else if (p[j -1] == '?' || s[i - 1] == p[j - 1])

                    {

                        lookup[i, j] = lookup[i - 1, j - 1];

                    }

                    else

                    {

                        lookup[i, j] = false;

                    }

                }

            }

            return lookup[s.Length, p.Length];

        }