给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘.’ 匹配任意单个字符
- ‘*’ 匹配零个或多个前面的那一个元素
- 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 ：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入：s = "ab", p = ".*" 输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
思路：
1、定义状态： 定义动态数组dp[m][n]
2.确定动态转移方程
说明： 为了区别dp数组与字符串索引的区别(因为相差1),我们设i=r-1,j=c-1(r为dp里面的行索引,c为dp里面的列索引)
2.1、当 s[i] = p[j] || p[j] == ‘.’ (即正好能够匹配或者相对应的是一个 .)，即动态转移方程为：dp[r][c]=dp[r-1][c-1]
2.2、当 p[j] == ’ * ’ (即匹配到了万能字符 * ) ;还需要区分两种情况
p[j-1] == s[i] || p[j-1] == ‘.’
两种情况分别对应的处理方式为：如果*的前一个字符正好对应了s,状态转移过程为:dp[r][c]=dp[r-1][c]
如果是 * 的前一个字符为 . 那我们只需要看 . 的前面字符匹配情况，状态转移过程为：dp[r][c]=dp[r][c-2]
其他情况:p[j-1] 不是s[i]或者. ；那么动态转移方程为: d[r][c] = dp[r][c-2]
3.确定边界条件
首先要确定dp[0][0],当p为空,s为空时，肯定是成功的！那么 dp[0][0]=true
当p为空字符串，而s 不为空时，dp数组必定为False，正好初始化dp数组的时候设置的是Fasle；即dp数组的第一列为False可以确定
当s为空字符串，而p不为空时，我们无需判断p里面的第一个值是否为"“，如果为”",那肯定匹配不到为Fasle,原数组正好是Fasle，所以直接从2开始判断即可。如果遇到了*,只要判断其对应的前面两个元素的dp值。
4.最终的结果
显然最终的结果是dp[m-1][n-1]的bool值
最后的dp数组为：
public boolean isMatch(String s, String p) {
//当一个数组为空时/两个都为空
if (s == null){
if (p == null){
return true;
}else return false;
}
// dp[i][j]:表示s的前i个字符，p的前j个字符
int m = s.length()+1;
int n = p.length()+1;
boolean[][] dp = new boolean[m][n];
//从右往左匹配，如果都能匹配上那两个字符串的零位都相等
dp[0][0] = true;// s为空，p为空，能匹配上
//文本串为空，模式串不为空。这里考虑一下末尾第一个字符是 * 的问题
//s为空，p不为空，由于*可以匹配0个字符，所以有可能为true;p往前再看一位,也就是[j - 2]
for (int j = 1;j < n;j++){
if (p.charAt(j-1) == '*'){
dp[0][j] = dp[0][j-2];
}
}
for (int r = 1;r < m;r++) {
int i = r - 1;
for (int c = 1; c < n; c++) {
int j = c - 1;
// 文本串和模式串末位字符能匹配上
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
dp[r][c] = dp[i - 1][j - 1];
} else if (p.charAt(j) == '*') {// 模式串*的前一个字符能够跟文本串的末位匹配上，p.charAt(j-1)表示模式串的前一个字符。
//此时前一个字符也可能是 ‘.’，所以也是能匹配上的情况
if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
dp[r][c] = dp[r - 1][c] || dp[r][c - 2];// 星号匹配0次的情况(就等于dp[r][c - 2] 本身);星号匹配1次或多次的情况
} else {// 模式串*的前一个字符不能够跟文本串的末位匹配
dp[r][c] = dp[r][c - 2]; // 向前再看一位，如果前一位是还是星号依然有机会
}
} else {
dp[r][c] = false;
}
}
}
return dp[m-1][n-1];
}
下面的代码可能好理解一些，但运行速度慢
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
//第?个是否匹配上
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
//看有没有可能,剩下的pattern匹配上全部的text
//看有没有可能,剩下的text匹配整个pattern
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
//没有星星的情况:第?个字符相等,?且剩下的text,匹配上剩下的pattern
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
