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 '*'
.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.
Two primary approaches effectively solve this problem:
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.
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]
.
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:
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.