44. Wildcard Matching

Time: O(m*n)

Space: O(m*n)

Intuition

DP table dp[i][j] = true if pattern p[0..j-1] matches string s[0..i-1]. Base: dp[0][0]=true; leading "*"s in p can match empty string. Transition: if p[j-1]=="?" or p[j-1]==s[i-1]: dp[i][j]=dp[i-1][j-1]. If p[j-1]=="*": dp[i][j] = dp[i-1][j] (star matches one more char) OR dp[i][j-1] (star matches nothing).

Algorithm

1Allocate dp[m+1][n+1] where m=s.Length, n=p.Length.
2dp[0][0] = true. For j from 1 to n: if p[j-1]=="*", dp[0][j] = dp[0][j-1].
3For i from 1 to m, j from 1 to n:
4 if p[j-1]=="?" or p[j-1]==s[i-1]: dp[i][j] = dp[i-1][j-1].
5 if p[j-1]=="*": dp[i][j] = dp[i-1][j] || dp[i][j-1].
6Return dp[m][n].

Example Walkthrough

Input: s = "adceb", p = "*a*b"

1.Leading "*" in p matches empty. dp[0][1]=true.
2."a" in p matches "a" in s. dp[1][2]=true.
3."*" matches any sequence -> dp[i][3]=true for all i>=1.
4."b" matches "b" (s[4]) using dp[4][3]=true -> dp[5][4]=true.

Output: true

Common Pitfalls

•A "*" can match zero characters - include dp[i][j-1] (star matches empty) in the OR condition.
•Pattern leading stars must initialise the top row of dp, not just dp[0][0].

44.cs

// Approach: DP table dp[i][j] = pattern[0..j] matches string[0..i].
// '?' matches any single char; '*' matches any sequence including empty.
// Time: O(m*n) Space: O(m*n)

public class Solution
{
    public bool IsMatch(string s, string p)
    {
        int n = p.Length;
        int m = s.Length;

        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++)
        {
            int[] arr = new int[m + 1];
            Array.Fill(arr, -1);
            dp[i] = arr;
        }

        //return topDown(n, m, p, s, dp);
        return tabulation(n, m, p, s);
    }

    private bool topDown(int i, int j, string p, string s, int[][] dp)
    {
        if (i == 0 && j == 0)
            return true;
        if (i == 0 && j > 0)
            return false;
        if (i > 0 && j == 0)
        {
            for (int k = 1; k <= i; k++)
            {
                if (p[k - 1] != '*')
                    return false;
            }
            return true;
        }

        if (dp[i][j] != -1)
            return dp[i][j] > 0;

        if (p[i - 1] == s[j - 1] || p[i - 1] == '?')
        {
            bool match = topDown(i - 1, j - 1, p, s, dp);
            dp[i][j] = match == true ? 1 : 0;
            return match;
        }

        if (p[i - 1] == '*')
        {
            bool sequence = topDown(i - 1, j, p, s, dp) || topDown(i, j - 1, p, s, dp);
            dp[i][j] = sequence == true ? 1 : 0;
            return sequence;
        }

        dp[i][j] = 0;
        return false;
    }

    private bool tabulation(int n, int m, string p, string s)
    {
        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++)
        {
            int[] arr = new int[m + 1];
            Array.Fill(arr, -1);
            dp[i] = arr;
        }
        dp[0][0] = 1;

        for (int j = 1; j <= m; j++)
            dp[0][j] = 0;

        for (int i = 1; i <= n; i++)
        {
            bool flag = true;
            for (int k = 1; k <= i; k++)
            {
                if (p[k - 1] != '*')
                {
                    flag = false;
                    break;
                }
            }
            dp[i][0] = flag == true ? 1 : 0;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (p[i - 1] == s[j - 1] || p[i - 1] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[i - 1] == '*')
                {
                    if (dp[i - 1][j] == 1 || dp[i][j - 1] == 1)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = 0;
                }
                else
                    dp[i][j] = 0;
            }
        }

        return dp[n][m] > 0;
    }
}

Was this solution helpful?