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 '*'.
Solutions
Solution 1: Memoization Search
Thinking
The first idea is recurse character by character: literals and ? match one, * eats empty or more. Correct, but without memo the * branches explode. \(|s|, |p| \le 2000\) will time out.
The bottleneck is asking the same suffix pair \((i, j)\) over and over. The state is only “does \(s[i:]\) match \(p[j:]\)”; subproblems overlap heavily.
Cache \(\textit{dfs}(i, j)\). The three * moves (consume one, advance both, skip *) are transitions on that state. Memoization turns exponential search into \(O(mn)\).
We design a function \(\textit{dfs}(i, j)\), which represents whether the string \(s\) starting from the \(i\)-th character matches the string \(p\) starting from the \(j\)-th character. The answer is \(\textit{dfs}(0, 0)\).
The execution process of the function \(\textit{dfs}(i, j)\) is as follows:
If \(i \geq \textit{len}(s)\), then \(\textit{dfs}(i, j)\) is true only when \(j \geq \textit{len}(p)\) or \(p[j] = '*'\) and \(\textit{dfs}(i, j + 1)\) is true.
If \(j \geq \textit{len}(p)\), then \(\textit{dfs}(i, j)\) is false.
If \(p[j] = '*'\), then \(\textit{dfs}(i, j)\) is true if and only if \(\textit{dfs}(i + 1, j)\) or \(\textit{dfs}(i + 1, j + 1)\) or \(\textit{dfs}(i, j + 1)\) is true.
Otherwise, \(\textit{dfs}(i, j)\) is true if and only if \(p[j] = '?'\) or \(s[i] = p[j]\) and \(\textit{dfs}(i + 1, j + 1)\) is true.
To avoid repeated calculations, we use the method of memoization search and store the result of \(\textit{dfs}(i, j)\) in a hash table.
The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.
Solution 1 already fills this match table from shorter prefixes to longer ones. The \(f[i][j]\) below is that same table.
Solution 1 already fills this table from shorter prefixes to longer ones.
Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).
Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):
If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.
Matching one character at a time is the natural first idea: a literal or ? consumes one character, and * consumes the empty string or any run. Both strings can have length \(2000\), and the first move on * is always \(\textit{dfs}(i+1, j)\), so that chain is as deep as \(|s|\) and exceeds the default recursion limit.
The same index pair is asked repeatedly, and whether two prefixes match depends only on shorter prefixes.
Let \(f[i][j]\) mean the first \(i\) characters of \(s\) match the first \(j\) characters of \(p\). The empty pair is true, and a run of * on the pattern inherits along \(j\). Filling \(i\) and \(j\) from small to large works because a * reads the cell above, the cell to the left, and the diagonal, while a literal or ? reads only the diagonal.
Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).
Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):
If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.