动态规划之正则表达
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 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
再次解决这道题！！！！！
方法一：DP table
在进行下面的处理之前，需要明确动态规划的几个步骤：
状态
首先状态 dp 一定能自己想出来。
==dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配==
转移方程
怎么想转移方程？首先想的时候从已经求出了 dp[i-1][j-1] 入手，再加上已知 s[i]、p[j]，要想的问题就是怎么去求 dp[i][j]。
已知 dp[i-1][j-1] 意思就是前面子串都匹配上了，不知道新的一位的情况。
那就分情况考虑，所以对于新的一位 p[j] s[i] 的值不同，要分情况讨论：
-
考虑最简单的 p[j] == s[i] : dp[i][j] = dp[i-1][j-1]
然后从 p[j] 可能的情况来考虑，让 p[j]=各种能等于的东西。 -
p[j] == "." : dp[i][j] = dp[i-1][j-1] -
p[j] ==" * "：
前两种情况比较容易解决，接下来就对几种情况分别进行讨论：
处理「*」 通配符
第一个难想出来的点：怎么区分 ‘*’ 的两种讨论情况
首先给了 ‘*’，明白 ‘*’ 的含义是 匹配零个或多个前面的那一个元素，所以要考虑他前面的元素 p[j-1]。‘*’ 跟着他前一个字符走，前一个能匹配上 s[i]，‘*’ 才能有用，前一个都不能匹配上 s[i]，‘*’ 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符
所以按照 p[j-1] 和 s[i] 是否相等，我们分为两种情况：
p[j-1] != s[i] : dp[i][j] = dp[i][j-2]
这就是刚才说的那种前一个字符匹配不上的情况。
比如(ab, abc * )。遇到 ‘ * ’ 往前看两个，发现前面 s[i] 的 ab 对 p[j-2] 的 ab 能匹配，虽然后面是 ‘c*’，但是可以看做匹配 0 次 c，相当于直接去掉 ’c * ‘，所以也是 true。注意 (ab, abc**) 是 False。
p[j-1] == s[i] or p[j-1] == "."：
' * ' 前面那个字符，能匹配 s[i]，或者 '*' 前面那个字符是万能的 .因为 '. *' 就相当于 '. .'，那就只要看前面可不可以匹配就行。
比如 (##b , ###b *)，或者 ( ##b , ### . * ) 只看 ### 后面一定是能够匹配上的。所以要看 b 和 'b *' 前面那部分 '##' 的地方匹不匹配。
第二个难想出来的点：怎么判断前面是否匹配
dp[i][j] = dp[i-1][j] // 多个字符匹配的情况
or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
or dp[i][j] = dp[i][j-2] // 没有匹配的情况
看 ### 匹不匹配，不是直接只看 ### 匹不匹配，要综合后面的 b* 来分析这三种情况是 or 的关系，满足任意一种都可以匹配上，同时是最难以理解的地方：
dp[i-1][j] 就是看 s 里 b 多不多， ### 和 ###b * 是否匹配，一旦匹配，s 后面再添个 b 也不影响，因为有 * 在，也就是 ###b 和 ###b *也会匹配。
dp[i][j-1] 就是去掉 * 的那部分，###b 和 ###b 是否匹配，比如 qqb qqb
dp[i][j-2] 就是 去掉多余的 b *，p 本身之前的能否匹配，###b 和 ### 是否匹配，比如 qqb qqbb* 之前的 qqb qqb 就可以匹配，那多了的 b * 也无所谓，因为 b * 可以是匹配 00 次 b，相当于 b * 可以直接去掉了。
三种满足一种就能匹配上。
为什么没有 dp[i-1][j-2] 的情况？ 就是 ### 和 ### 是否匹配？因为这种情况已经是 dp[i][j-1] 的子问题。也就是 s[i]==p[j-1]，则 dp[i-1][j-2]=dp[i][j-1]。
最后来个归纳：
如果 p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]；
如果 p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1]；
如果 p.charAt(j) == '*'：
如果 p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]
如果 p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.'：
dp[i][j] = dp[i-1][j]
or dp[i][j] = dp[i][j-1]
or dp[i][j] = dp[i][j-2]
完整代码：
public boolean isMatch(String s,String p){
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
for (int i = 0; i < p.length(); i++) { // here's the p's length, not s's
if (p.charAt(i) == '*' && dp[0][i - 1]) {
dp[0][i + 1] = true; // here's y axis should be i+1
}
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {//如果是任意元素 或者是对于元素匹配
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {//如果前一个元素不匹配 且不为任意元素
dp[i + 1][j + 1] = dp[i + 1][j - 1];
} else {
dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
/*
dp[i][j] = dp[i-1][j] // 多个字符匹配的情况
or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
or dp[i][j] = dp[i][j-2] // 没有匹配的情况
*/
}
}
}
}
return dp[s.length()][p.length()];
}
C++代码：
class Solution {
public:
// 动态规划
bool isMatch(string s, string p) {
int ns = s.size();
int np = p.size();
if(p.empty()) //注意这里判断的写法，不能是if(p.empty() || s.empty());原因试一下就知道啦
return s.empty();
vector<vector<bool>> dp(ns+1, vector<bool>(np+1, false));
//就是博客中的问题，怎么判断前面是否匹配，相当于提前把遇到‘*’的情况在dp[i][j - 2]
//的情况先记录下来，后面使用，因为初始化的时候全部都是false，所以要提前处理
dp[0][0] = true;
for(int i = 1; i <= np; i++)
{
if(i-2 >= 0 && p[i-1] == '*' && p[i-2])
{
dp[0][i] = dp[0][i-2];
}
}
for(int i = 1; i <= ns; i++)
{
for(int j = 1; j <= np; j++)
{
if(p[j-1] == s[i-1] || p[j-1] == '.')
dp[i][j] = dp[i-1][j-1];//万金油，直接相等
if(p[j-1] == '*')
{
bool zero, one;
if(j-2 >= 0)
{
zero = dp[i][j-2];//匹配0次，
one = (p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j];//匹配1次
dp[i][j] = zero || one;//有一个为真即可
}
}
}
}
return dp[ns][np];
}
};
方法二： 动态规划
第⼀步， 我们暂时不管正则符号， 如果是两个普通的字符串进⾏⽐较， 如何
进⾏匹配？ 我想这个算法应该谁都会写：
bool isMatch(string text, string pattern) {
if (text.size() != pattern.size())
return false;
for (int j = 0; j < pattern.size(); j++) {
if (pattern[j] != text[j])
return false;
}
return true;
}
然后， 稍微改造⼀下上⾯的代码， 略微复杂了⼀点， 但意思还是⼀样的，很容易理解吧：
bool isMatch(string text, string pattern) {
int i = 0; // text 的索引位置
int j = 0; // pattern 的索引位置
while (j < pattern.size()) {
if (i >= text.size())
return false;
if (pattern[j++] != text[i++])
return false;
}
// 相等则说明完成匹配
return j == text.size();
}
如上改写， 是为了将这个算法改造成递归算法（伪码） ：
def isMatch(text, pattern) -> bool:
if pattern is empty: return (text is empty?)
first_match = (text not empty) and pattern[0] == text[0]
return first_match and isMatch(text[1:], pattern[1:])
处理点号「.」 通配符
点号可以匹配任意⼀个字符， 万⾦油嘛， 其实是最简单的， 稍加改造即可：
def isMatch(text, pattern) -> bool:
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
return first_match and isMatch(text[1:], pattern[1:])
处理「*」 通配符
星号通配符可以让前⼀个字符重复任意次数， 包括零次。 那到底是重复⼏次
呢？ 这似乎有点困难， 不过不要着急， 我们起码可以把框架的搭建再进⼀
步：
def isMatch(text, pattern) -> bool:
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
# 发现 '*' 通配符
else:
return first_match and isMatch(text[1:], pattern[1:])
星号前⾯的那个字符到底要重复⼏次呢？ 这需要计算机暴⼒穷举来算， 假设
重复 N 次吧。 前⽂多次强调过， 写递归的技巧是管好当下， 之后的事抛给递归。 具体到这⾥， 不管 N 是多少， 当前的选择只有两个： 匹配 0 次、 匹
配 1 次。 所以可以这样处理：
if len(pattern) >= 2 and pattern[1] == '*':
return isMatch(text, pattern[2:]) or \
first_match and isMatch(text[1:], pattern)
# 解释： 如果发现有字符和 '*' 结合，
# 或者匹配该字符 0 次， 然后跳过该字符和 '*'
# 或者当 pattern[0] 和 text[0] 匹配后， 移动 text
可以看到， 我们是通过保留 pattern 中的「*」 ， 同时向后推移 text， 来实现
「」 将字符重复匹配多次的功能。 举个简单的例⼦就能理解这个逻辑了。 假
设 pattern = a , text = aaa， 画个图看看匹配过程：
选择使⽤「备忘录」 递归的⽅法来降低复杂度
我将暴⼒解法和优化解法放在⼀起， ⽅便你对⽐，
# 带备忘录的递归
def isMatch(text, pattern) -> bool:
memo = dict() # 备忘录
def dp(i, j):
if (i, j) in memo: return memo[(i, j)]
if j == len(pattern): return i == len(text)
first = i < len(text) and pattern[j] in {text[i], '.'}
if j <= len(pattern) - 2 and pattern[j + 1] == '*':
ans = dp(i, j + 2) or \
first and dp(i + 1, j)
else:
ans = first and dp(i + 1, j + 1)
memo[(i, j)] = ans
return ans
return dp(0, 0)
# 暴⼒递归
def isMatch(text, pattern) -> bool:
if not pattern: return not text
first = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return isMatch(text, pattern[2:]) or \
first and isMatch(text[1:], pattern)
else:
return first and isMatch(text[1:], pattern[1:])
评论区