这是遇到的第一个困难题，自己先写了一遍，结果被边界条件绕晕了，不过和递归方法的思想还是一致的。关键点就在于*，*可以匹配0次或多次，放在递归条件里，每一步判断，其实就是匹配或者不匹配。
递归方法解法如下：
class Solution {
public boolean isMatch(String s, String p) {
if (p.isEmpty()) {
return s.isEmpty();
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0)
|| p.charAt(0) == '.');
if (p.length() >= 2 && p.charAt(1) == '*') {
return (firstMatch && isMatch(s.substring(1), p))
|| isMatch(s, p.substring(2));
} else {
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}
下面还会看下动态规划的解法，动态规划在于找到临界点和迭代表达式，这里的dp[i][j]代表第i位和第j位以后的字符串是够匹配，i代表s的下标，j代表p的下标。
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// s位置为i，p位置为j是否能匹配，比着下标大1
boolean[][] dp = new boolean[m + 1][n + 1];
// s和p都为空的情况，能匹配
dp[0][0] = true;
// i从0开始，代表s为空时也也能进行匹配
for (int i = 0; i <= m; i++) {
// j从1开始，说明p为空时不能匹配上，默认为false即可
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// s当前位置，和p前一个位置如果相同
if (isMatch(s, p, i, j - 1)) {
// s当前位置，和p前一个位置如果相同,有两种选择
// 1.不匹配a*组合，那么取决于dp[i][j - 2]
// 2.用*匹配，要看i - 2到j - 1位置是否能匹配
dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
} else {
// 不同的话，代表这个*只能取0，那么依赖于dp[i][j - 2]是否可匹配
dp[i][j] = dp[i][j - 2];
}
} else {
// 当前位置相同，且之前也匹配
dp[i][j] = isMatch(s, p, i, j) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
/**
* 判断s,p对应位置上是否匹配，i，j代表位置，而非下标
*/
public boolean isMatch(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (s.charAt(i - 1) == p.charAt(j - 1)) {
return true;
}
return p.charAt(j - 1) == '.';
}
网友评论