面试题19. 正则表达式匹配
正则表达式匹配
题目描述
请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
示例：
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
输入:
s = "aa"
p = "a"
输出: true
解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入:
s = "ab"
p = "."
输出: true
解释: "." 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
题目分析
正则式匹配哈，这还不简单，return s.matches(p)，完事......
哈哈哈这样做当然能AC，但是不怕被打吗，下面介绍两种方法，第一种是常规的思路，第二种是第一种的动态规划版改进法；
方法1
实例： s - aaa；p - ab*ac*a
-
我们从两个字符串的最后一位看起，a和a相等，两者往前走一位；
1
-
现在当前位不等，且p的当前位为*，因为*可以让*前面的字符出现0-无数次，所以就看*前面的字符和s的当前位相等不相等；
2.1 如果不相等，*就可以让前面的字符出现零次，p往前走两步（相当于删除了c*），s不动，继续比较；
2.2 如果相等，这就复杂一点；
aaa和a*，这个*可以让p最后一个a出现多次，把s全匹配了；
a和aa*，这个*就可以让p最后一个a出现0次；
ba和ba*，这个*就可以让p最后一个a出现一次；
对于实例，显然是2.1的情况，接着分析；
2
-
现在当前位显然相等，也就是1的情况，都往前走一步
3
-
这里遇到了*，对应2.1的情况，p往前走两步，s不动
4
5.最后一个都相等，完事。
5
- 1和2基本把情况都列举了，最后两种情况很简单，第一种就是当前位不相等，且不含有*，直接返回不匹配就可以；第二种就是p的当前位为 . ，那就和第一种情况一样；
- 这种做法可以直接用递归来实现，不足的地方就是从后面往前推的时候，多次调用了isMatch，但是没有把结果保存起来，造成冗余的计算，所以第二种方法采用DP的方式，从头开始匹配，并将匹配结果保存起来；
public boolean isMatch(String s, String p) {
int len2 = p.length() - 1;
int len1 = s.length() - 1;
return isMatch(s, p, len1, len2);
}
public boolean isMatch(String s, String p, int a, int b) {
// 同时到达最前面，相同
if (a == -1 && b == -1)
return true;
// b没了，a还有，肯定错
if (b == -1)
return false;
// a没了，b还有，如果b含有*，就往前走两步，继续比
if (a == -1 && p.charAt(b) == '*')
return isMatch(s, p, a, b - 2);
// a没了，b还有，且不是*，则肯定不等
else if (a == -1 && p.charAt(b) != '*')
return false;
// b有一个.，可以都往前走
if (p.charAt(b) == '.')
return isMatch(s, p, a - 1, b - 1);
// 两者相同，都往前走
if (s.charAt(a) == p.charAt(b))
return isMatch(s, p, a - 1, b - 1);
// 两者不相同，且b并不是*，肯定不等，false
if (p.charAt(b) != '*')
return false;
// b为*，如果b的前一个和a相等，a往前走或ab往前走或b往前走
if (p.charAt(b - 1) == s.charAt(a) || p.charAt(b - 1) == '.')
return isMatch(s, p, a - 1, b) || isMatch(s, p, a - 1, b - 2) || isMatch(s, p, a, b - 2);
// b为*，如果b的前一个和a不相等，b往前走两步
return isMatch(s, p, a, b - 2);
}
方法2
从方法1里我们可以总结出从后往前推的规律了，这里我们从前往后推的规律也差不多，我就不画图了，直接上结论：
s和p都从第一位开始比较：
1 如果两者当前位s[i]和p[j]相等，或者p的当前位为 . ，那么当前位的匹配是成功的，当前串的匹配结果取决于match[i-1][j-1]，即match[i][j] = match[i-1][j-1]
2 如果当前位s[i]和p[j]不相等，且p[j]不是*，那么当前位的匹配直接是失败的，即match[i][j] = false；
3 如果当前位s[i]和p[j]不相等，且p[j]是*，这里还是和方法1一样分三种情况
3.1 p[j-1] != s[i]且p[j-1] != ‘.’，那么*就让p[j-1]出现0次，当前串的结果和i、j-2的结果没区别（相当把这两个字符串删去），即match[i][j] = match[i][j-2]
3.2 p[j-1] == s[i] ，这也是和第一种方法一样分三种情况
3.2.1 *让p[j-1]出现0次，即和3.1一样，match[i][j] = match[i][j-2]；
3.2.2 *让p[j-1]出现1次，即和1一样，match[i][j] = match[i][j-1]；
3.2.3 *让p[j-1]出现多次，这就相当于把s[i]删除掉，即match[i][j] = match[i-1][j]；
情况大概就是上面那些，但是按照这个思路写的代码提交上去之后发现出了问题：
输入:
"aab"
"cab"
输出
false
预期结果
true
惨兮兮，看了题解（这个题解还是cxx同学写的）之后发现有一点小bug，参照cxx的建议就成功AC了；
(https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/dong-tai-gui-hua-hui-su-by-caixiaoxin/)
public boolean dpSolution(String s, String p) {
boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
match[0][0] = true;
for (int i = 1; i < match.length; i++) {
for (int j = 1; j < match[0].length; j++) {
if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
match[i][j] = match[i - 1][j - 1];
continue;
}
if (p.charAt(j - 1) != '*') {
match[i][j] = false;
continue;
}
if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
match[i][j] = match[i][j - 2];
continue;
}
match[i][j] = match[i][j - 2] || match[i][j - 1] || match[i-1][j];
}
}
for (int i = 1; i < match.length; i++) {
for (int j = 1; j < match[0].length; j++) {
System.out.print(match[i][j]+" ");
}
System.out.println();
}
return match[s.length()][p.length()];
}
image.png
