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'.
Example 4:
**Input:** s = "adceb", p = "*a*b"
**Output:** true
**Explanation:** The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
**Input:** s = "acdcb", p = "a*c?b"
**Output:** false
Constraints:
0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.
ac1: 2D dp
similar with #10
class Solution {
public boolean isMatch(String s, String p) {
// edge cases
if (s == null || p == null) return false;
// initialize
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 1; i < dp[0].length; i++) {
// s is empty, p has to be all "*" to be true.
if (p.charAt(i-1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
// walk, function transformation
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') {
dp[i][j] = dp[i-1][j-1];
}
if (p.charAt(j-1) == '*') {
dp[i][j] = dp[i][j-1] || dp[i-1][j];
}
}
}
// result
return dp[s.length()][p.length()];
}
}
/*
state: dp[i][j], s.substring(0, i) and p.substring(0, j) is match
function:
1. if p.charAt(j-1) == s.charAt(i-1) , dp[i][j] = dp[i-1][j-1];
2. if p.charAt(j-1) == '?' , dp[i][j] = dp[i-1][j-1];
3. if p.charAt(j-1) == '*' :
(1) * means empty: dp[i][j] = dp[i][j-1];
(2) * means anything: dp[i][j] = dp[i-1][j];
initialize: dp[0][0] = true; dp[0][i]
result: dp[s.length()][p.length()]
*/
ac2: 1D DP
Notice: 1D dp, need to update each one in the array, because it does not have default value, unlike 2D dp. else dp[j] = false;
class Solution {
public boolean isMatch(String s, String p) {
// edge cases
if (s == null || p == null) return false;
// initialize
boolean[] dp = new boolean[p.length()+1];
dp[0] = true;
for (int i = 1; i < dp.length; i++) {
if (p.charAt(i-1) == '*') {
dp[i] = true;
} else {
break;
}
}
// walk, function transformation
for (int i = 1; i <= s.length(); i++) {
boolean prev = dp[0];
dp[0] = false;
for (int j = 1; j < dp.length; j++) {
boolean tmp = dp[j];
if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') {
dp[j] = prev;
} else if (p.charAt(j-1) == '*') {
dp[j] = dp[j-1] || dp[j];
} else {
dp[j] = false;
}
prev = tmp;
}
}
// result
return dp[p.length()];
}
}
ac3: 2 pointers
class Solution {
public boolean isMatch(String s, String p) {
// edge cases
if (s == null || p == null) return false;
// 2 pointers, walk
int si = 0, pi = 0, starIndex = -1, sRestart = 0;
while (si < s.length()) {
if (pi < p.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?') ) {
si++;
pi++;
}
else if (pi < p.length() && p.charAt(pi) == '*') {
starIndex = pi;
sRestart = si;
pi++;
}
// s.charAt(si) != p.charAt(pi)
else if (starIndex != -1) { // meet * before, let * kill one char in s
sRestart++;
si = sRestart;
pi = starIndex + 1;
}
else {
return false;
}
}
// check pattern remaining
while (pi < p.length() && p.charAt(pi) == '*') {
pi++;
}
// if match, pi should hit the end of pattern
return pi == p.length();
}
}
/*
2 pointers
si, pi
if s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?' , move on, si++; pi++;
if p.charAt(pi) == '*': meet * , starI = pi, sRestart = si(in case * will offset chars in s), pi++
if s.charAt(si) != p.charAt(pi):
1) have * before starI != -1 : '*' can kill char in s one by one
sRestart++; si = sRestart; (the * offset one char in s)
pi = starI + 1;
2) don't have *, return false;
abededab
?b*d**
a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d, check if there was a *, yes, ss++, s=ss; p=star+1 // the * offset 'e'
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;
*/