剑指Offer 19.正则表达式匹配
示例 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 的小写字母以及字符 . 和 *，无连续的 ‘*’。
分析
对于两个字符串的题目，例如最长公共子序列，一般都是转化为求s1[:n]是否能和s2[:m]匹配，即s1的前n个字符组成的子字符串能否和s2的前m个字符组成的子字符串匹配，通过求解子问题来获得原问题的解，典型的二维动态规划问题。
解题思路
总体思路是一个逐步匹配的过程，从s[:1]和p[:1]是否匹配开始判断，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串s和p。
- 对于
p中一个字符而言，它只能在s中匹配一个字符，匹配的方法具有唯一性 - 对于
p中字符+星号的组合而言，它可以在s中匹配任意自然数个字符，并不具有唯一性
状态定义
定义f[i][j]表示s的前i个字符与p中的前j个字符是否能够匹配
状态转移方程
状态转移方程要根据==普通字符、.、\*==这三种字符的功能来分析。
f[0][0]代表的是空字符串的状态，f[i][j]对应添加的字符实际是s[i-1]和p[j-1]。状态转移方程：
-
当
p[j-1]=普通字符时，f[i][j]在以下情况为true时等于true-
f[i-1][j-1]且s[i-1]=p[j-1]：即s前i-2个字符组成的子串和p前j-2个字符组成的子串匹配的同时，s[i-1]与p[j-1]也相同
-
-
当
p[j-1]='.'时，f[i][j]在以下情况为true时等于true-
f[i-1][j-1]：即s前i-2个字符组成的子串和p前j-2个字符组成的子串匹配，此时p[j-1]='.'可以看作任意字符
-
-
当
p[j-1]='*'时，表示可以对p的第j-2个字符匹配任意自然数次，p[j-2]*要整体考虑- 在匹配0次时，
f[i][j]=f[i][j-2]，即s的前i-1个字符组成的子串是否和p的前j-1个字符组成的子串能否匹配取决于s的前i-1个字符组成的子串是否和p的前j-3个字符组成的子串匹配，直接舍弃了p的p[j-2]*这后两个字符
- 在匹配0次时，
- 在匹配1次时，
f[i][j]=f[i-1][j-2],if s[i-1]=p[j-2]，即s的前i-1个字符组成的子串是否和p的前j-1个字符组成的子串能否匹配取决于s的前i-2个字符组成的子串是否和p的前j-3个字符组成的子串能否匹配，此时需s[i-1]=p[j-2]*，p[j-2]*等效于一个字符p[j-2]
- 在匹配2次时，
f[i][j]=f[i-2][j-2],if s[i-2]=s[i-1]=p[j-2]，即s的前i-1个字符组成的子串是否和p的前j-1个字符组成的子串能否匹配取决于s的前i-3个字符组成的子串是否和p的前j-3个字符组成的子串能否匹配，此时需是s[i-2]s[i-1]=p[j-2]*，p[j-2]*等效于两个字符p[j-2]p[j-2]
- 在匹配3次时，
f[i][j]=f[i-3][j-2],if s[i-3]=s[i-2]=s[i-1]=p[j-2]，即s的前i-1个字符组成的子串是否和p的前j-1个字符组成的子串能否匹配取决于s的前i-4个字符组成的子串是否和p的前j-3个字符组成的子串能否匹配，此时需是s[i-3]s[i-2]s[i-1]=p[j-2]*，p[j-2]*等效于3个字符p[j-2]p[j-2]p[j-2]
-
如果这样任意次匹配下去就需要枚举
p[j-1]*到底匹配了s中几个字符，会增加编程难度；实际上只需要考虑两种情况：- 情况一：匹配0次，即直接舍弃
p的p[j-2]*这后两个字符，f[i][j]=f[i][j-2] - 情况二：匹配1次，即只匹配
s末尾的一个字符，此时可以利用之前子问题的结果，s的前i-1个字符和p的前j-1个字符是否匹配取决于s的前i-2个字符是否和p的前j-1个字符匹配，f[i][j]=f[i-1][j],if s[i-1]=p[j-1] or p[j-1]='.'
- 情况一：匹配0次，即直接舍弃
f [ i ] [ j ] = { f [ i − 1 ] [ j ] o r f [ i ] [ j − 2 ] , s [ i − 1 ] = p [ j − 2 ] o r p [ j − 2 ] = ′ . ′ f [ i ] [ j − 2 ] , s [ i − 1 ] ≠ p [ j − 2 ] f[i][j]=\left\{\begin{matrix} f[i-1][j] & or & f[i][j-2] &,& s[i-1]=p[j-2] & or & p[j-2]='.' \\ f[i][j-2] & , & s[i-1] \ne p[j-2] \end{matrix}\right. f[i][j]={f[i−1][j]f[i][j−2]or,f[i][j−2]s[i−1]=p[j−2],s[i−1]=p[j−2]orp[j−2]=′.′
综上，状态转移方程为
f
[
i
]
[
j
]
=
{
i
f
(
p
[
j
−
1
]
≠
′
∗
′
)
=
{
f
[
i
−
1
]
[
j
−
1
]
,
s
[
i
−
1
]
=
p
[
j
−
1
]
o
r
p
[
j
−
1
]
=
′
.
′
f
a
l
s
e
,
o
t
h
e
r
w
i
s
e
i
f
(
p
[
j
−
1
]
=
′
∗
′
)
=
{
f
[
i
−
1
]
[
j
]
o
r
f
[
i
]
[
j
−
2
]
,
s
[
i
−
1
]
=
p
[
j
−
2
]
o
r
p
[
j
−
2
]
=
′
.
′
f
[
i
]
[
j
−
2
]
,
o
t
h
e
r
w
i
s
e
f[i][j]=\begin{cases} if(p[j-1]\ne '*' )= \left\{\begin{matrix} f[i-1][j-1] &,& s[i-1]=p[j-1] & or & p[j-1]='.'\\ false & , & otherwise \end{matrix}\right. \\ if(p[j-1]='*')=\left\{\begin{matrix} f[i-1][j] & or & f[i][j-2] &,& s[i-1]=p[j-2] & or & p[j-2]='.'\\ f[i][j-2] & , & otherwise \end{matrix}\right. \end{cases}
f[i][j]=⎩⎪⎪⎨⎪⎪⎧if(p[j−1]=′∗′)={f[i−1][j−1]false,,s[i−1]=p[j−1]otherwiseorp[j−1]=′.′if(p[j−1]=′∗′)={f[i−1][j]f[i][j−2]or,f[i][j−2]otherwise,s[i−1]=p[j−2]orp[j−2]=′.′
边界条件
动态规划的边界条件为 f[0][0]=true，即两个空字符串是可以匹配的。最终的答案即为f[m][n]，其中 m和 n 分别是字符串 s 和 p 的长度。
复杂度
时间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中 m 和 n 分别是字符串 s 和 p 的长度
空间复杂度： O ( m n ) O(mn) O(mn)，即为存储所有状态使用的空间
实现代码
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*') {
f[i][j] = f[i][j-2] || i && f[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.');
} else {
f[i][j] = i && f[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
}
}
}
return f[m][n];
}
};