LC44. Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
这题和LC10. Regular Expression很像，都是String的匹配。但是区别在于这题的*是可以匹配任何Series，和其前面的char无关。’?’和’.’ 的作用相同。
two pointers solution
LC10我想用双指针结果交了无数次没有AC…这里由于*和前面的字符没有关系所以用双指针可解。分为几种情况，如果匹配则进行下一个字符的匹配，如果遇到🌟的话就记录当前位置并继续匹配，如果不匹配就回到上一个🌟的位置，改变🌟匹配series的长度继续匹配。
public class Solution {
public boolean isMatch(String s, String p) {
// two pointers
if(s == null || p == null) return false;
char[] sarr = s.toCharArray();
char[] parr = p.toCharArray();
int i = 0, j = 0, star = -1, begin = 0;
while(i < sarr.length){
// if match or ?
if(j < parr.length && (sarr[i] == parr[j] || parr[j] == '?')){
i++;
j++;
// * match until not match, if not match backtracking to next char
}else if(j < parr.length && parr[j] == '*'){
while(j < parr.length && parr[j] == '*') j++;
if(j == parr.length) return true; // last is *
star = j;
begin = i;
// when * and not match
}else if(star >= 0){
i = ++begin;
j = star;
}else return false;
} // while i,j
while(j < parr.length && parr[j] == '*') j++;
return i == sarr.length && j == parr.length;
}
}
其实我觉得这个不是O(n)…Backtracking最差的话会搞到O(n!)吧QAQ..事实证明two pointers的做法确实比DP快了很多。
⚠️：由于有可能匹配到最后p还有好多***但是s已经匹配完，所以while里是以s作为判断，最后再判断有可能有末尾的🌟存在。
DP solution
和LC10一样可以利用DP来解决， DP{i}{j}代表s[i-1]与p[j-1]是否匹配。初始化对于p前置*的DP矩阵都置为true。可以匹配时DP{i}{j} = DP{i-1}{j-1}, 遇到🌟时可能匹配一串字符或者不匹配字符，不匹配就对应DP{i}{j-1}, 一串则对应DP{i-1}{j}。
public class Solution {
public boolean isMatch(String s, String p) {
// DP
if(s == null || p == null) return false;
char[] sarr = s.toCharArray();
char[] parr = p.toCharArray();
boolean[][] dp = new boolean[sarr.length+1][parr.length+1];
dp[0][0] = true;
for(int i = 1; i <= parr.length; i++){
if(parr[i-1] == '*') dp[0][i] = true;
else break;
}
for(int i = 1; i <= sarr.length; i++){
for(int j = 1; j <= parr.length; j++){
if(sarr[i-1] == parr[j-1] || parr[j-1] == '?'){
dp[i][j] = dp[i-1][j-1];
}else if(parr[j-1] == '*'){
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
} // for j
} // for i
return dp[sarr.length][parr.length];
}
}
复杂度O(n^2), O(n^2)， 这个解法也比较好理解。
⚠️：各处的“=”
没10个提交都不能AC的QAQ