昨天没有发做题笔记，因为昨天骑车子把腿和手摔破了，疼得一逼，然后还在公司写了一天代码，惨。。回家之后磨蹭了一会儿，看了这道题Wildcard Matching，写了二维DP的解法结果commit的时候一直提示wrong answer，就去睡觉了。今天又来看这题了。另，今天是覃超《硅谷之路》的大结局呢。。有点伤感。覃超的讲话风格很像飞哥。。表情夸张那种。。上了两个月的课挺舍不得的。
首先是DP做法，二维DP：
public boolean isMatch(String s, String p) {
if (s == null && p == null) return true;
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 1; i < p.length() + 1; i++) {
if (p.charAt(i - 1) == '*') {
//必须是p的前i-1个char都是*，s才能跟它匹配
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < p.length() + 1; j++) {
if (p.charAt(j - 1) != '*') {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i-1][j];
}
}
}
return dp[s.length()][p.length()];
}
这题的方程有点难以理解的是dp[i-1][j];这个代表，p的第j位是*，所以p连同这一位j看看是否可以匹配s的前i-1位，因为s的第i位一定是可以匹配的。比如:
s: aaba
p: aa*
这里*就可以匹配ba两位。
另外，还有一种扫描的方法，用两个指针，one for string, one for pattern，从头到尾扫描。复杂度是O(m + n)。我就画了个图简单看了下。
boolean comparison(String str, String pattern) {
int s = 0, p = 0, match = 0, starIdx = -1;
while (s < str.length()){
// advancing both pointers
if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// * found, only advancing pattern pointer
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;
match = s;
p++;
}
// last pattern pointer was *, advancing string pointer
else if (starIdx != -1){
p = starIdx + 1;
match++;
s = match;
}
//current pattern pointer is not star, last patter pointer was not *
//characters do not match
else return false;
}
//check for remaining characters in pattern
while (p < pattern.length() && pattern.charAt(p) == '*')
p++;
return p == pattern.length();
}
