题目描述
给你一个字符串 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
算法1
(动态规划) $O(nm)$
状态表示:
$f[i][j]$表示$s$的前$i$个字符,$p$的前$j$个字符是否匹配。
初始化:
$f[0][0] = true;$ 空字符串和空字符串是匹配的。
状态转移:
如果$p$的第$j$个字符不是星号,必须$s$的第$i$个字符和$p$的第$j$个字符匹配,$s$的前$i - 1$个字符和$p$的前$j - 1$个字符是匹配的才行, 有
$f[i][j] = isMatch(s[i - 1], p[j - 1]) && f[i - 1][j - 1];$
如果是星号,有两种情况:
1.星号表示0个字符,那么有
$f[i][j] = f[i][j - 2];$
2.若星号表示非0个字符,那么首先$s$的第$i$个字符必须与星号前的字符,同时,除去前面这对匹配的字符,$s$的前$i - 1$个字符与$p$的前$j$个字符也应该是匹配的,有
$f[i][j] = f[i][j - 2] || (f[i - 1][j] && isMatch(s[i - 1], p[j - 2]));$
时间复杂度
参考文献
C++ 代码
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
int f[m + 1][n + 1]; memset(f, 0, sizeof f);
f[0][0] = true;
for (int j = 1; j <= n; ++j)
f[0][j] = j >= 2 && p[j - 1] == '*' && f[0][j - 2];
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (p[j - 1] != '*') f[i][j] = isMatch(s[i - 1], p[j - 1]) && f[i - 1][j - 1];
else f[i][j] = j >= 2 && (f[i][j - 2] || f[i - 1][j] && isMatch(s[i - 1], p[j - 2]));
return f[m][n];
}
bool isMatch(char c_s, char c_p){
return c_s == c_p || c_p == '.';
}
};
空间优化版本,空间优化成一维
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
int f[n + 1]; memset(f, 0, sizeof f);
f[0] = true;
for (int j = 1; j <= n; ++j)
f[j] = j >= 2 && p[j - 1] == '*' && f[j - 2];
for (int i = 1; i <= m; ++i){
f[0] = false;
bool pre = i == 1;
for (int j = 1; j <= n; ++j){
bool tmp = f[j];
if (p[j - 1] != '*') f[j] = isMatch(s[i - 1], p[j - 1]) && pre;
else f[j] = j >= 2 && (f[j - 2] || f[j] && isMatch(s[i - 1], p[j - 2]));
pre = tmp;
}
}
return f[n];
}
bool isMatch(char c_s, char c_p){
return c_s == c_p || c_p == '.';
}
};