问题
问能否用模式串p完全匹配字符串s。模式串中’?’代表匹配单个字符,’*’代表匹配空或多个字符
算法:线性DP
这道题与LC 10 正则表达式非常相似,我们同样规定f[i][j] = s[1~i]和p[1~j]是否匹配
容易想到平凡转移:f[i][j] = f[i-1][j-1] && (s[i] == p[j] || p[j] == ?)
难点在于引入*
后的非平凡转移。要归纳这种转移,最关键的是要将可能的选择归类。
当我们遇到p[j]=='*'
时,我们有哪些选择?答案是,要么丢掉,要么利用。
如果丢掉,则应当从f[i][j-1]
转移过来;如果利用,则应当从f[i-1][j]
转移。
这里我刚开始有个疑惑:如果利用,那么用'*'
匹配第一个字符应该从哪里转移呢?比如abdc
的b
和a*c
的*
匹配?不应该是f[i-1][j-1]
吗?当然,也可以,答案也不会错,但是其实没必要分这个类。因为我们丢弃'*'
的选项已经帮我们做了这件事: a
与a*
匹配了,所以ab
也可以与a*
匹配。
复杂度
时空均为:$O(NM)$
代码
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
s = ' '+s, p = ' '+p; // 避免用偏移量
vector<vector<bool>> f(m+1, vector<bool>(n+1));
f[0][0] = true;
for(int i = 0; i <= m; i ++){
for(int j = 1; j <= n; j ++){
f[i][j] = (s[i] == p[j] || p[j] == '?') && i && f[i-1][j-1];
if(p[j] == '*'){
f[i][j] = f[i][j-1] || i && f[i-1][j]; //丢弃* 或者 用*匹配
}
}
}
return f[m][n];
}
};