题目描述
请实现一个函数用来匹配包含 '. ' 和 '' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '' 表示它前面的字符可以出现任意次（含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 的小写字母，以及字符 . 和 *。
题解
定义状态
使用动态规划的方法，首先是定义状态，dp[i][j]代表 s 的前 i 个字符串s[0, i)与 p 的前 j 个字符串是否匹配。
边界条件
- 两个空字符串一定匹配，从代码角度来看，对于 s：
a， p：a，dp[1][1] = dp[0][0]，故dp[0][0] = true - p 为空时，两个字符串一定不匹配，故
dp[i][0] = false - s 为空且 p 中对应元素为星号时，p 中的星号可以让星号前面一个元素消失，故
dp[0][j]=dp[0][j-2]
接下来分情况讨论。
一、s 对应元素与 p 对应元素相等，s[i-1] == p[j-1]
此时dp[i][j] = dp[i-1][j-1]
二、s 对应元素与 p 对应元素不相等，s[i-1] != p[j-1]
这里又分为三种情况：
-
p[j-1] = '.'，点代表任意一个字符，相当于s[i-1] == p[j-1]，此时dp[i][j] = dp[i-1][j-1] -
p[j-1] = '*'，星号代表前面的那个字符可以出现任意次，这里又分为三种情况，分别是星号代表前面0个字符、1个字符以及n个字符的情况。- 例如，s：
aab，p：aabb*，星号匹配 0 个前面的那个字符，可将星号和星号前面的字符删除，则dp[i][j] = dp[i][j-2]; - 例如，s：
aab，p：aab*，星号匹配 1 个前面的那个字符，此时dp[i][j-1]已经匹配，即如果s[i-1] == p[j-2] || p[j-2] == '.'，可将星号删除，则dp[i][j] = dp[i][j-1] - 例如，s：
aabbbbbbbb，p：aab*，星号匹配 n 个前面的那个字符，即dp[i][j] = dp[i-1][j]
- 例如，s：
-
s[i-1] != p[j-1]，字符串本身不相等，直接判定不匹配，dp[i][j] = false;
参考代码
public boolean isMatch(String s, String p) {
int sLength = s.length(), pLength = p.length();
if (sLength == 0 && pLength == 0)
return true;
boolean[][] dp = new boolean[sLength+1][pLength+1];
// 边界条件：
// 初始化dp数组，两个空字符串一定匹配，故dp[0][0]=true
// p为空时，两个字符串一定不匹配，故dp[i][0] = false
// s为空且p中对应元素为星号时，p中的星号可以让星号前面一个元素消失，故dp[0][j]=dp[0][j-2]
dp[0][0] = true;
for (int j = 1; j <= pLength; j++) {
if (p.charAt(j-1) == '*')
dp[0][j] = dp[0][j-2];
}
for (int i = 1; i <= sLength; i++) {
for (int j = 1; j <= pLength; j++) {
// 若s和p中两个字符相等
if (s.charAt(i-1) == p.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
// 若s和p中两个字符不相等
else {
// 当p中对应字符为点时，相当于两个字符相等
if (p.charAt(j-1) == '.')
dp[i][j] = dp[i-1][j-1];
// 当p中对应字符为星号时，分情况讨论
else if (p.charAt(j-1) == '*') {
// 只有在s当前元素与p中星号前面的一个元素匹配时，让星号匹配1个或n个前面的那个字符
if (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.')
dp[i][j] = dp[i][j-1] || dp[i-1][j];
// 不论s当前元素与p中星号前面的一个元素是否匹配，都将星号和星号前面的一个字符删除，让星号匹配0个前面的那个字符
dp[i][j] = dp[i][j] || dp[i][j-2];
}
// p中对应字符不为点也不为星号，两个字符一定不相等
else dp[i][j] = false;
}
}
}
return dp[sLength][pLength];
}
