44. Wildcard Matching - cocoder39/coco39_LC GitHub Wiki
Notes 2020:
similar to 10. Regular Expression Matching
Option 1: dp
class Solution:
def isMatch(self, s: str, p: str) -> bool:
dp = [[False] * (len(p)+1) for i in range(len(s)+1)]
dp[-1][-1] = True
for i in range(len(s), -1, -1):
for j in range(len(p)-1, -1, -1):
if p[j] == '*':
dp[i][j] = dp[i][j+1] or (i < len(s) and dp[i+1][j])
else:
dp[i][j] = i < len(s) and p[j] in {'?', s[i]} and dp[i+1][j+1]
return dp[0][0]
Option 2: recursion + memo
(sCur < len(s) and helper(sCur+1, pCur))
only if s[sCur] is a valid char then we can do helper(sCur+1, pCur)). That's why we need to check sCur < len(s)
- time complexity: O(s * p) as we need to fill each entry in memo
- space complexity: O(s * p) for memo and O(s+p) for call stack
class Solution:
def isMatch(self, s: str, p: str) -> bool:
def helper(sCur, pCur):
if sCur in memo and pCur in memo[sCur]:
return memo[sCur][pCur]
if pCur == len(p):
return sCur == len(s)
res = False
if p[pCur] == '*':
res = helper(sCur, pCur+1) or (sCur < len(s) and helper(sCur+1, pCur))
else:
res = sCur < len(s) and p[pCur] in {'?', s[sCur]} and helper(sCur+1, pCur+1)
memo[sCur][pCur] = res
return res
memo = collections.defaultdict(dict)
return helper(0, 0)
Option 3: iteration
time complexity is O(s * p). EG, for example below, '*' will match 0 char, then 1 char, then 2 chars ...
s = aaaaaaa....b
p = *aaaaab
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s_len, p_len = len(s), len(p)
s_idx, p_idx = 0, 0
star_idx, s_tmp_idx = -1, -1
while s_idx < s_len:
if p_idx < p_len and p[p_idx] in {'?', s[s_idx]}:
s_idx += 1
p_idx += 1
elif p_idx < p_len and p[p_idx] == '*':
# optimistic match: assuming there is a match without using '*'
star_idx = p_idx
s_tmp_idx = s_idx
p_idx += 1
elif star_idx == -1: # mismatch + no start was found
return False
else:
p_idx = star_idx + 1
s_idx = s_tmp_idx + 1
s_tmp_idx = s_idx
for i in range(p_idx, p_len):
if p[i] != '*':
return False
return True
========================================================================
time is O(m * n) and memory is O(m * n)
bool isMatch(string s, string p) {
int m = s.length();
int n = p.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[i][0] = false;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = dp[0][i - 1] && p[i -1] == '*';
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] != '*') {
dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '?');
}
else { // empty || at least one char
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[m][n];
}
memory can be optimized to O(n)
dp[cur][0] = false works as
for (int i = 1; i <= m; i++) {
dp[i][0] = false;
}
in above code
bool isMatch(string s, string p) {
int m = s.length();
int n = p.length();
//dp[pre][j] = true if s[0 .. i] matches p[0 .. j]
//dp[cur][j] = true if s[0 .. i + 1] matches p[0 .. j]
vector<vector<bool>> dp(2, vector<bool>(n + 1));
dp[0][0] = true;
//dp[1][0] = false;
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && p[j -1] == '*';
}
int pre = 0, cur = 1;
for (int i = 1; i <= m; i++) {
dp[cur][0] = false; //bug if miss this line
for (int j = 1; j <= n; j++) {
if (p[j - 1] != '*') {
dp[cur][j] = dp[pre][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '?');
}
else { // empty || at least one char
dp[cur][j] = dp[cur][j - 1] || dp[pre][j];
}
}
swap(cur, pre);
}
return dp[pre][n];
}
second round: how to use ''
case 1: '' matches empty => dp[i][j] = dp[i][j - 1]
case 2: '' matches one or more sequence => * matches ab works as a* matches ab where '' matches empty or sequence after 'a' (exactly definition of '*') => dp[i][j] = dp[i - 1][j]
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); //dp[i][j] = true if p[0..j-1] matches s[0..i-1]
/*
for (int i = 0; i <= m; i++) {
if (i != 0) {
dp[i][0] = false;
} else {
dp[0][0] = true;
}
}
*/
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
dp[0][i] = dp[0][i - 1] && p[i - 1] == '*';
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] != '*') {
dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '?');
} else {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[m][n];
}
optimize memory with rolling array. take care dp[i][0]
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(2, vector<bool>(n + 1)); //dp[i][j] = true if p[0..j-1] matches s[0..i-1]
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
dp[0][i] = dp[0][i - 1] && p[i - 1] == '*';
}
int pre = 0, cur = 1;
for (int i = 1; i <= m; i++) {
if (i > 1) {
dp[pre][0] = false;
}
dp[cur][0] = false;
for (int j = 1; j <= n; j++) {
if (p[j - 1] != '*') {
dp[cur][j] = dp[pre][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '?');
} else {
dp[cur][j] = dp[cur][j - 1] || dp[pre][j];
}
}
swap(pre, cur);
}
return dp[pre][n];
}
recursion: time complexity is too high to pass
"aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba"
"a*******b"
bool isMatch(string s, string p) {
if (p.empty()) {
return s.empty();
} else if (p[0] == '*') {
return isMatch(s, p.substr(1)) || (! s.empty() && isMatch(s.substr(1), p));
} else {
return ! s.empty() && (p[0] == s[0] || p[0] == '?') && isMatch(s.substr(1), p.substr(1));
}
}
iteration: kinda greedy. match as much as you can, once you can not match, go back and use '*' to match the unmatched char. time is O(m * n)
bool isMatch(string s, string p) {
int unmatchs, star = -1;
int i = 0, j = 0;
while (i < s.length()) {
if (p[j] == s[i] || p[j] == '?') {
i++; j++; continue;
} else if (p[j] == '*') {
unmatchs = i; star = j++; continue;
} else if (star >= 0) { //have met '*' before
i = ++unmatchs; j = star + 1; continue; //use '*' to match unmatchs, ++unmatchs for repeated '*'
} else { //i doesn't reach the end but there is unmatch
return false;
}
}
while (j < p.length() && p[j] == '*') j++;
return j == p.length();
}