Given input string s and pattern p with ? and * support, implement wildcard matching. ? matches any single character, * matches any sequence (including empty).
Input: s="aa", p="a" → Output: falseInput: s="adceb", p="*a*b" → Output: true
DP: dp[i][j] = whether s[0..i-1] matches p[0..j-1]. For *, dp[i][j] = dp[i-1][j] (use one char) || dp[i][j-1] (match empty).
- dp[0][0]=true; dp[0][j]=true if all p[0..j-1] are *.
- If p[j-1]==* : dp[i][j] = dp[i-1][j] || dp[i][j-1].
- If p[j-1]==? or matches s[i-1]: dp[i][j] = dp[i-1][j-1].
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++) dp[0][j] = dp[0][j-1] && p.charAt(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];
else if (p.charAt(j-1) == '?' || p.charAt(j-1) == s.charAt(i-1)) dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)