Leetcode 44. Wildcard Matching

 44.Wildcard Matching

Hard, Dynamic Programming

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

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

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

 

Example 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"

Output: true

Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"

Output: false

Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

 

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

 To solve the Wildcard Matching problem, we can use Dynamic Programming (DP) to systematically compare the string s and the pattern p. The idea is to build a table that tracks whether a substring of s matches a substring of p.

---

Key Observations:

1. ? matches exactly one character.
2. * matches zero or more characters.
3. The solution involves comparing substrings while handling the flexibility introduced by *.

---

Approach:

1. Define DP Table:

   • Let dp[i][j] be a boolean indicating whether the first i characters of s match the first j characters of p.

2. Initialization:

   • dp[0][0] = true: Both strings are empty.
   • dp[0][j] = true if all previous characters in p are *: A * can match an empty string.
   • dp[i][0] = false for i > 0: A non-empty s cannot match an empty p.

3. Recurrence Relation:

   • If p[j-1] == s[i-1] or p[j-1] == '?', dp[i][j] = dp[i-1][j-1].
   • If p[j-1] == '*', dp[i][j] = dp[i-1][j] (match * with one character) or dp[i][j-1] (match * with zero characters).

4. Result:

   • The answer is in dp[s.Length][p.Length].

---

Implementation:

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];
        
        // Base cases
        dp[0,0] = true; // Empty string matches empty pattern
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];
            }
        }
        
        // Fill the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
                    dp[i, j] = dp[i - 1, j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i, j] = dp[i - 1, j] || dp[i, j - 1];
                }
            }
        }
        
        return dp[m, n];
    }
}

---

Explanation of Code:

1. Base Case:

   • An empty string and pattern match (dp[0][0] = true).
   • A pattern with only * can match an empty string.

2. Dynamic Programming Table:

   • For each i and j, we check:
     • If characters match or there's a ?, copy the diagonal value (dp[i-1][j-1]).
     • If there’s a *, check:
       • Match zero characters: dp[i][j-1].
       • Match one or more characters: dp[i-1][j].

3. Final Result:

   • dp[m][n] holds whether the entire string matches the entire pattern.

---

Complexity Analysis:

1. Time Complexity:

   • Filling the DP table requires $O(m \times n)$ operations, where $m$ is the length of s and $n$ is the length of p.

2. Space Complexity:

   • The DP table takes $O(m \times n)$ space.
   • Space optimization (using a rolling array) can reduce this to $O(n)$.

---

Example Outputs:

Example 1:

• Input: s = "aa", p = "a"
• Output: false

Example 2:

• Input: s = "aa", p = "*"
• Output: true

Example 3:

• Input: s = "cb", p = "?a"
• Output: false

This implementation ensures correctness and efficiency for the given constraints.