44. Wildcard Matching

This problem asks to implement wildcard pattern matching with support for ? (matches any single character) and * (matches any sequence of characters, including the empty sequence). The matching must cover the entire input string.

Solution Approaches

Two primary approaches effectively solve this problem:

1. Memoization Search (Top-Down DP): This approach uses recursion with memoization to avoid redundant computations. A recursive function dfs(i, j) checks if the substring of s starting at index i matches the substring of p starting at index j. Memoization stores the results of these subproblems to accelerate the process.

2. Dynamic Programming (Bottom-Up DP): This approach uses a 2D table dp[i][j] where dp[i][j] is true if the first i characters of s match the first j characters of p, and false otherwise. The table is filled iteratively, starting from base cases and building up to the final result dp[s.length][p.length].

Time and Space Complexity Analysis

Both approaches have the same time and space complexity:

• Time Complexity: O(m * n), where m is the length of string s and n is the length of string p. This is because both approaches explore all possible combinations of matching substrings.

• Space Complexity:

  • Memoization: O(m * n) due to the memoization table (or call stack in some implementations without explicit memoization).
  • Dynamic Programming: O(m * n) due to the DP table.

Code Implementation (Multiple Languages)

The following code demonstrates both approaches in several programming languages:

Memoization (Python):

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @lru_cache(None)  # Using lru_cache for memoization
        def dfs(i, j):
            if i == len(s):
                return j == len(p) or (p[j] == '*' and dfs(i, j + 1))
            if j == len(p):
                return False
            if p[j] == '*':
                return dfs(i + 1, j) or dfs(i, j + 1)  # * matches 0 or more
            return (p[j] == '?' or s[i] == p[j]) and dfs(i + 1, j + 1)
 
        return dfs(0, 0)
 

Dynamic Programming (Java):

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
 
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
        }
 
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // * matches 0 or more
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

(Other languages like C++, Go, TypeScript, C#, etc., would follow similar structures for both approaches.) The core logic remains consistent across languages; only syntax and data structure specifics change. Remember to adapt the code to handle edge cases (empty strings, etc.) appropriately.