题目描述
blablabla
样例
blablabla
递归做法 O(n^2) O(1)(尾部递归)
思路
两个指针p1, p2一起从s, p头部向后走,以p[p2 + 1] 是否为 * 分情况讨论
- 若为 * ,* 可匹配 当前字符p[p2] 的任意多个(非确定有限状态机)
- 若s[p1] == p[p2] || p[p2] == ‘.’,则可以进行多种动作(所以要使用递归实现)
- p1不动,p2后跳2字符(忽略*)
- p1后跳1,p2不动(保持当前状态)
- p1后跳1,p2后跳2(进入下一状态)
- 否则p2向后跳两个字符
- 若s[p1] == p[p2] || p[p2] == ‘.’,则可以进行多种动作(所以要使用递归实现)
- 若不为 * ,则直接匹配即可
O(nm) O(nm)
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
if(!n && !m) return true;
if(n && !m) return false;
return MatchCore(s, p, 0, 0);
}
bool MatchCore(string& s, string& p, int i, int j) {
if(i == s.size() && j == p.size()) return true;
if(i != s.size() && j == p.size()) return false;
// 需要对 s 遍历到尾部,p还没到尾部的情况进行特判,剑指offer中用的c语言,不判断越界访问
if(i == s.size() && j != p.size()) {
if(j+1 < p.size() && p[j+1] == '*') return MatchCore(s, p, i, j+2);
return false;
}
if(j+1 < p.size() && p[j + 1] == '*'){
if(s[i] == p[j] || p[j] == '.') {
return MatchCore(s, p, i, j+2) || MatchCore(s, p, i+1, j) || MatchCore(s, p, i+1, j+2);
}
else
return MatchCore(s, p, i, j+2);
}
if(s[i] == p[j] || p[j] == '.') return MatchCore(s, p, i+1, j+1);
return false;
}
};
递归 + 记忆数组
滚动数组的原始版本
f[i][j]表示s[0..i]与p[0..j]是否匹配,需要特判s或p为空的情况,需要初始化第0行和第0列,并对j == 1的情况进行额外处理,主要目的是理解初始化的意义以及简便方法的合理性
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
// 判断s或p为空的情况
if(!n || !m) {
if(!n && !m) return true;
// s 为空时,若p为a*b*..的形式,可以匹配
if(!n) {
if(m % 2 == 0){
bool flag = true;
for(int i = 1;i < n;i += 2)
if(p[i] != '*') flag = false;
if(flag) return true;
}
}
return false;
}
vector<vector<bool>> f(n, vector<bool>(m));
// 初始化 f[i][0] f[0][i]
if(s[0] == p[0] || p[0] == '.') f[0][0] = true;
if(f[0][0] && p[1] == '*') f[0][1] = true;
for(int i = 1;i < m;i++) {
if(p[i] != '*') {
bool flag = true;
if(i % 2 == 0){
for(int j = 1;j < i;j += 2)
if(p[j] != '*') flag = false;
if(flag && (s[0] == p[i] || p[i] == '.')) f[0][i] = true;
}
}
else{
f[0][i] = f[0][i-1];
}
}
for(int i = 1;i < n;i++) {
for(int j = 1;j < m;j++){
if(p[j] != '*') {
f[i][j] = f[i-1][j-1] && (s[i] == p[j] || p[j] == '.');
}
else{
// j=1时,需要进行特判
if(j == 1) f[i][1] = f[i-1][1] && (s[i] == p[0] || p[0] == '.');
if(j > 1) f[i][j] = f[i][j-2] || f[i-1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
}
}
return f[n-1][m-1];
}
};
滚动数组的进阶版
填充一个相同字符,可以大大减少边界和初始化的处理
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
// 填充一个相同元素,后续方便进行边界处理
s = ' ' + s, p = ' ' + p;
vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
// f[0][0]可以处理s、p均为空的边界
f[0][0] = true;
// for(int i = 1;i <= m;i++){
// if(p[i] == '*')
// f[0][i] = f[0][i-2];
// }
// i的下标为什么从0开始?s[0], p[0,..j]有可能匹配,需要计算f[0][j]
for(int i = 0;i <= n;i++){
// j的下标为什么从1开始? 因为f[i][0], i>=1 一定为0,不需要进行计算
for(int j = 1;j <= m;j++){
if(i && p[j] != '*') {
f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
}
else if(j > 1 && p[j] == '*'){
// i == 0时,其实就是判断s为空,p不为空是否匹配
// 可与下面写成一行,这样更方便理解
if(!i) f[0][j] = f[0][j-2];
else f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
}
}
return f[n][m];
}
};