这是LeetCode上面一道难度为困难的题目，记录一下，整的来说，递归方法描述起来思路清晰，动态规划描述需要借用一定的图画或者表格手段。
正则表达式匹配
请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
递归解法：
public boolean isMatch(String t, String p) {
// 递归的边界值，当t的长度为0的时候
if (t.length()==0) {
// p必须是（字符+*）的结构，所以长度需要为偶数
if (p.length()%2!=0) return false;
// 查找*号，如果有单独的字符，立刻返回false
for (int i = 0; i < p.length(); i+=2) {
if (p.charAt(i)!='*') {
return false;
}
}
return true;
}
// 当p为""的时候返回false
if (p.length()==0) {
return false;
}
// 获取t和p第一位
char t0 = t.charAt(0),p0 = p.charAt(0),p1 = 0;
// p1为p的第二位
if (p.length()>1) {
p1 = p.charAt(1);
}
// 如果p1不为*号，则当前位必须匹配
if (p1!='*') {
// t0==p0或者p0为'.'，当前位置匹配成功，匹配后续
if (t0==p0||p0=='.') {
return isMatch(t.substring(1),p.substring(1));
} else {
return false;
}
} else {
// p1为*号，则存在两种情况
// 1.c*为空
// 2.c*为多个c
// 匹配当前字段
if (t0==p0||p0=='.') {
// 当前字段匹配成功，则有两种情况
// 1.后续需要再次匹配
// 2.跳过c*的匹配
return isMatch(t.substring(1),p) || isMatch(t,p.substring(2));
} else {
// 匹配失败，尝试匹配跳过c*的部分
return isMatch(t,p.substring(2));
}
}
}
动态规划解法：
// 正序解法，从长度0到长度n
public boolean isMatch(String t, String p) {
int n = t.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
// dp数组里包含了从长度为0，到长度为n,m的所有情况
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 空正则串的情况
if (j == 0) {
// 空正则的情况下，只有t为空字符串的时候匹配为true
dp[i][j] = (i == 0);
} else {
//非空正则分为两种情况
// 长度为j的正则字符串的最后一个字符为“*”
// 与不为“*”的情况
if (p.charAt(j - 1) != '*') {
// 当前正则串的字符的尾字符不是“*”
// 字符床长度都大于0，且尾字符相等，或者p的尾字符为'.'的时候，当前字符匹配成功，dp[i][j]=dp[i-1][j-1]
// 否则匹配失败使用默认的false
if (i > 0 && j > 0 && (t.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
// 当前正则串的字符的尾字符是“*”
// 假设c*的个数为0,则直接忽略正则的两个字符
if (j >= 2 ) {
dp[i][j] = dp[i][j - 2];
}
// c*匹配多个字符的时候
// t的长度必须大于1,否则按照c*为0即可获得true
// 接下来判断正则字符串p的倒数第二个字符和t的尾巴字符是否相等
// 或者是否为'.'
// 满足条件，则当前字符匹配成功
if (i >= 1 && j >= 2 && (t.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
// 当前字符匹配功后，即可忽略t的尾字符串
// 即d[i][j] = dp[i-1][j]
// 这里或上c*个数为0的情况，得到最后结果
dp[i][j] |= dp[i - 1][j];
}
}
}
}
}
// 返回长度为n,m的两个字符串的匹配结果
return dp[n][m];
}
// 逆序解法，从最后一个字符开始匹配
public boolean isMatch(String t, String p) {
// 存储匹配状态，默认为false
boolean[][] memo = new boolean[t.length()+1][p.length()+1];
// 初始化""与""的匹配结果，为true
memo[t.length()][p.length()] = true;
// i代表t的第i位，j代表p的第j位
// i = t.length 代表 ""
for (int i = t.length();i>=0;i--) {
for (int j = p.length() - 1; j >= 0; j--) {
// 如果t[i]==p[j]或者p[j]=='.' 则认为当前字符匹配成功
boolean first = i < t.length() && (t.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
// 如果p[j]后面跟了一个*号
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// 将c*视为0个的时候，即当前跳过p[j]和p[j+1](c*两个字符)匹配t[i]与p[j+2]
// 将c*视为多个的时候，即视作当前字符匹配成功与匹配t[i+1]与p[j]的结果
// （"ab"匹配"a*b",在"b"与"a*b"的匹配中，走了a*为0的条件）
// ex : t[aa] p[a*] memo[2][2] = true
// ex : t[2] p[2->0] memo[2][1] = false memo[2][0] = true
// ex : t[1] p[2->0] memo[1][2] = false memo[1][1] = false memo[1][0] = true
// ex : t[0] p[2->0] memo[0][2] = false memo[0][1] = false memo[0][0] = true
memo[i][j] = memo[i][j + 2] || first && memo[i + 1][j];
} else {
// p[j]后面没有*号
// 判断当前字符是否相等与t[i+1] p[j+1] 匹配结果
memo[i][j] = first && memo[i + 1][j + 1];
}
}
}
// 返回t[0]和p[0]的比较结果
return memo[0][0];
}
