给你一个字符串 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 = "cab"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5：
输入：s = "mississippi" p = "misisp*."
输出：false
提示：
- 0 <= s.length <= 20
- 0 <= p.length <= 30
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 。
- 保证每次出现字符
*时，前面都匹配到有效的字符
Leetcode 10
⼀、不考虑通配符情况
第⼀步，我们暂时不管正则符号，如果是两个普通的字符串进⾏⽐较，如何 进⾏匹配？我想这个算法应该谁都会写：
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 = aa，画个图看看匹配过程：
假设主串为 A，模式串为 B 从最后一步出发，需要关注最后进来的字符。假设 A 的长度为 n ，B 的长度为 m ，关注正则表达式 B 的最后一个字符是谁，它有三种可能，正常字符、* 和 .（点），那针对这三种情况讨论即可，如下：
- 如果 B 的最后一个字符是正常字符，那就是看
A[n-1]是否等于B[m-1]，相等则看 \(A_{0..n-2}\) 与 \(B_{0..m-2}\)，不等则是不能匹配，这就是子问题。 - 如果 B的最后一个字符是
.，它能匹配任意字符，直接看 \(A_{0..n-2}\)与 \(B_{0..m-2}\) - 如果 B的最后一个字符是
*它代表B[m-2]=c可以重复0次或多次，它们是一个整体c*:
情况一：A[n-1]是 0 个 c，B 最后两个字符废了，能否匹配取决于 \(A_{0..n-1}\) 和\( B_{0..m-3}\)是否匹配（只能选不看c*这一种情况）
情况二：\(A[n-1]\)是多个 \(c\) 中的最后一个（这种情况必须 \(A[n-1]=c\) 或者c='.'），所以A匹配完往前挪一个，B继续匹配，因为可以匹配多个，继续看 \(A_{0..n-2}\)和 \(B_{0..m-1}\)是否匹配。（这里可以选择不看，或者看两种情况）
⾄此，正则表达式算法就基本完成了，
四、递归思路
我们同样可以把上述过程用递归表达式表示出来。
注意递归和状态转移方程式相反的方向。状态转移是通过\(f[i-1][j-1]\)推导\(f[i][j]\)。而递归框架是考虑\(f[i-1][j-1]\)的时候带入\(dfs(f[i][j])\)的情况。
代码
class Solution {
public:
bool isMatch(string s, string p) {
// 如果字符串长度为0，需要检测下正则串
if(s.size()==0){
if(p.size()%2!=0) return false;
// 如果正则串长度为奇数，必定不匹配，比如 "."、"ab*",必须是 a*b*这种形式，*在奇数位上
for(int i=1;i<p.size();i=i+2){
if(p[i]!='*') return false;
}
return true;
}
// 如果字符串长度不为0，但是正则串没了，return false
if(p.size()==0) return false;
//后一位分为是 '*' 和不是 '*' 两种情况
char a = s[0], b = p[0], c = p.size()>1?p[1]:0;
if(c=='*'){
// 如果该位字符一样，或是正则串该位是 '.'，有看和不看两种情况
if(a==b||b=='.'){
return isMatch(s,p.substr(2))||isMatch(s.substr(1),p);
}else{
return isMatch(s,p.substr(2));
}
}
// 如果该位字符一样，或是正则串该位是 '.',也就是能匹配任意字符，就可以往后走
if(a==b||b=='.'){
return isMatch(s.substr(1),p.substr(1));
}
return false;
}
};五、动态规划
转移方程
\(f[i][j]\)代表 A 的前\(i\)个和 B 的前\(j\)个能否匹配
- 对于前面两个情况，可以合并成一种情况 \(f[i][j] = f[i-1][j-1]\)
- 对于第三种情况，对于
c*分为看和不看两种情况- 不看：直接砍掉正则串的后面两个，\( f[i][j] = f[i][j-2]\)
- 看：正则串不动，主串前移一个，\(f[i][j] = f[i-1][j]\)
初始条件
特判：需要考虑空串空正则
- 空串和空正则是匹配的，\(f[0][0] = true\)
- 非空串和空正则必不匹配，\(f[1][0]=...=f[n][0]=false\)
- 空串和非空正则，不能直接定义
true和false，必须要计算出来。（比如\(A= '' \) ,\(B=a*b*c*\)） - 非空串和非空正则，那肯定是需要计算的了。
大体上可以分为空正则和非空正则两种，空正则也是比较好处理的，对非空正则我们肯定需要计算。
非空正则的三种情况，前面两种可以合并到一起讨论，第三种情况是单独一种，那么也就是分为当前位置是 * 和不是 *两种情况了。
我们开数组要开 \(n+1\)，这样对于空串的处理十分方便。结果就是 \(f[n][m]\)
代码如下
将上述结果合并一下，就得到我们的暴力递归算法：
# 暴⼒递归
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:])我选择使⽤「备忘录」递归的⽅法来降低复杂度。有了暴⼒解法，优化的过程及其简单，就是使⽤两个变量 i, j 记录当前匹配到的位置，从⽽避免使⽤⼦字符串切⽚，并且将 i, j 存⼊备忘录，避免重复计算即可。
优化解法⽆⾮就是把暴⼒解法「翻译」了⼀遍，加了个 memo 作为备忘录，仅此⽽已。
# 带备忘录的递归
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)c++代码
typedef map<pair<int,int>,bool> pmap;
class Solution {
pmap dict;// 备忘录
/*也可以使用vector<vector<int> > dict(ns,vector<int>(np,-1));
0 表示 false
1 表示 true
-1 表示没有遍历到*/
public:
bool isMatch(string s, string p) {
return dp(s,p,0,0);
}
bool dp(string s, string p,int i, int j){
int ns = s.length();
int np = p.length();
bool ans;
pmap::iterator it = std::find_if(
dict.begin(),dict.end(),[=](const pair<pair<int,int>,bool> && a){
pair<int,int> location = a.first;
return location.first == i && location.second == j;
});
if(it != dict.end()) return it->second; //在备忘录里，直接返回
if(j==np) return i ==ns;
bool first = i<ns && (p[j]==s[i] || p[j]=='.'); //匹配当前
if(j<=np - 2 && p[j+1]=='*'){ //发现'*'
ans = dp(s,p,i,j+2) //'*'匹配0个
|| (first&&dp(s,p,i+1,j)); //'*'匹配一个
}else{
ans = first && dp(s,p,i+1,j+1); //没有'*'，都往后挪一个
}
dict.insert(make_pair(make_pair(i,j),ans));
return ans;
}
};自底向上代码：
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size();
int m = p.size();
vector<vector<bool>> f(n + 1,vector<bool>(m + 1,0));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//分成空正则和非空正则两种
if (j == 0) {
f[i][j] = i == 0;
continue;
}
//非空正则分为两种情况* 和 非*
//注意这里f[i][j]代表第i和j配，但是对应s的下标是i-1!
if (p[j - 1] != '*') {
if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) {
f[i][j] = f[i - 1][j - 1];
}
continue;
}
//碰到 * 了，分为看和不看两种情况
//不看
if (j >= 2) {
f[i][j] = f[i][j] || f[i][j - 2];
}
//看
if (i >= 1 && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) {
f[i][j] = f[i][j] || f[i - 1][j];
}
}
}
return f[n][m];
}
};六、重叠子问题定性判断
有的读者也许会问，你怎么知道这个问题是个动态规划问题呢，你怎么知道它就存在「重叠⼦问题」呢，这似乎不容易看出来呀？
解答这个问题，最直观的应该是随便假设⼀个输⼊，然后画递归树，肯定是可以发现相同节点的。这属于定量分析。
其实不⽤这么⿇烦，下⾯我来教你定性分析，⼀眼就能看出「重叠⼦问题」性质。
先拿最简单的斐波那契数列举例，我们抽象出递归算法的框架：
def fib(n):
fib(n - 1) #1
fib(n - 2) #2看着这个框架，请问原问题 f(n) 如何触达⼦问题 f(n - 2) ？有两种路径，⼀ 是 f(n) -> #1 -> #1, ⼆是 f(n) -> #2。前者经过两次递归，后者进过⼀次递归⽽已。两条不同的计算路径都到达了同⼀个问题，这就是「重叠⼦问题」****。
⽽且可以肯定的是，只要你发现⼀条重复路径，这样的重复路径⼀定存在千 万条，意味着巨量⼦问题重叠。
同理，对于本问题，我们依然先抽象出算法框架：
def dp(i, j):
dp(i, j + 2) #1
dp(i + 1, j) #2
dp(i + 1, j + 1) #3提出类似的问题，请问如何从原问题 dp(i, j) 触达⼦问题 dp(i + 2, j + 2) ？⾄ 少有两种路径，⼀是 dp(i, j) -> #3 -> #3，⼆是 dp(i, j) -> #1 -> #2 -> #2。因此，本问题⼀定存在重叠⼦问题，⼀定需要动态规划的优化技巧来处理。
七、最后总结
通过本⽂，你深⼊理解了正则表达式的两种常⽤通配符的算法实现。其实点 号「.」的实现及其简单，关键是星号「*」的实现需要⽤到动态规划技巧， 稍微复杂些，但是也架不住我们对问题的层层拆解，逐个击破。另外，你掌握了⼀种快速分析「重叠⼦问题」性质的技巧，可以快速判断⼀个问题是否 可以使⽤动态规划套路解决。
回顾整个解题过程，你应该能够体会到算法设计的流程：从简单的类似问题 ⼊⼿，给基本的框架逐渐组装新的逻辑，最终成为⼀个⽐较复杂、精巧的算 法。所以说，读者不必畏惧⼀些⽐较复杂的算法问题，多思考多类⽐，再⾼ ⼤上的算法在你眼⾥也不过⼀个脆⽪。