题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持'.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符
'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
样例
-
示例 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
- 提示：
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从a-z的小写字母。
p 可能为空，且只包含从a-z的小写字母，以及字符.和*。
保证每次出现字符*时，前面都匹配到有效的字符
题目评估
知识点：动态规划
难度：困难（真的好难，呜呜呜~）
分析
这题给我整蒙了，目前还没有完全透彻的搞懂，放个官方题解吧。
Java代码题解
class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true; // s和p长度都为0匹配成功
// 注意：这里i从0开始，即使s长度为0也可能匹配成功
for (int i = 0; i < dp.length; i++) {
// 注意：这里j从1开始，因为p长度为0，如果s长度不为0，一定匹配失败
for (int j = 1; j < dp[i].length; j++) {
if (p.charAt(j - 1) == '*') { // 如果当前p[j]为*
if (match(s, p, i, j - 1)) { // 看一下s[i]和p[j-1]是否一样
// 如果它们一样，p中*前边的字符在s中多次出现的 或 在s中只出现一次
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
// 如果*前字符不匹配，直接不管“字符+*”的组合，返回上一个字符串的匹配结果
dp[i][j] = dp[i][j - 2];
}
} else { // p[j]不是*
if (match(s, p , i ,j)) { // 匹配一下s[i]和p[j]是否一样
// 掐掉当前头后的字符串后的匹配情况和当前字符串的匹配情况相同
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = false; // 如果当前字符都不一样，直接false
}
}
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
private boolean match(String s, String p, int i, int j) {
if (i == 0) { // 如果s长度为0直接返回false
return false;
} else if (p.charAt(j - 1) == '.') { // ‘.’匹配任何字符
return true;
} else {
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
}
复杂度分析
设n为s字符串的长度，m为p字符串的长度，双层遍历两个字符串，时间复杂度为：O(nm)，由于开辟了一个n+1行m+1列的数组，所以空间复杂度为O(nm)。