题目描述
请实现一个函数用来匹配包括'.'
和'*'
的正则表达式。
模式中的字符'.'
表示任意一个字符,而'*'
表示它前面的字符可以出现任意次(含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。
例如,字符串"aaa"
与模式"a.a"
和"ab*ac*a"
匹配,但是与"aa.a"
和"ab*a"
均不匹配。
数据范围
输入字符串长度 [0,300]。
样例
输入:
s="aa"
p="a*"
输出:true
算法 dp
分析
状态表示:f[i][j]
表示p从j开始到结尾,是否能匹配s从i开始到结尾,即 s[i...]
和p[j...]
是否匹配
状态转移
1. p[j]
是正常字符:f[i][j] = s[i] == p[j] && f[i + 1][j + 1]
2. p[j]
是'.'
:f[i][j] = f[i + 1][j + 1]
3. p[j + 1]
是 '*'
:f[i][j] = f[i][j + 2] || f[i + 1][j]
特殊情况:f[n][m] = true
; 字符串为空
其中,前两种情况可以归纳为第一个字符是否匹配,这样就可以
1. p[j + 1] 不是'*'
:f[i][j]为真 <= s[i]匹配p[j] && f[i+1][j+1]为真
2. p[j + 1]是'*'
:满足下列条件时为真
1) 匹配0个:p[i][j+2]
为真
2) 匹配任意个:f[i+1][j]
为真(这里存在枚举p[j]匹配多个的情况,但是这种枚举操作都包含在了f[i+1][j]中)
时间复杂度 $O(nm)$
状态数量: s长度*p长度 nm
状态转移:$O(1)$
C++ 代码
class Solution {
public:
vector<vector<int>> f;
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
return dp(0, 0, s, p);
}
bool dp(int x, int y, string &s, string &p)
{
if(f[x][y] != -1) return f[x][y]; //已经算过
if(y == m) //模式串p匹配结束
return f[x][y] = x == n;
bool first_match = x < n && (s[x] == p[y] || p[y] == '.'); //s[i] == p[j]或者p[j]=='.'
bool ans;
if(y + 1 < m && p[y + 1] == '*') //p[j + 1] = '*'
ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
else
ans = first_match && dp(x + 1, y + 1, s, p);
return f[x][y] = ans;
}
};
总结
做了好几次还是不会状态讨论,需要多积累积累