题目描述
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
1. '?' 可以匹配任何单个字符。
2. '*' 可以匹配任意字符序列（包括空字符序列）。
3. 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
-
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。 -
示例 2：
输入：s = "aa", p = ""
输出：true
解释：'' 可以匹配任意字符串。 -
示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。 -
提示：
0 <= s.length, p.length <= 2000 s 仅由小写英文字母组成 p 仅由小写英文字母、'?' 或 '*' 组成
分析
状态s[0..j] & p[0..i] 的匹配情况可以推出下一状态 s[0..j+1] & p[0..i/i+1] 的匹配情况。
存在'*'匹配0个或多个，因此状态推导关系不仅仅是一维的。
问题可以分解为若干 重叠子问题 ：二者的子串匹配 --> 子问题之间存在 二维的状态推导关系 --> 二维动态规划 。
状态推导
设dp[i][j]表示s[0..j-1] & p[0..i-1]的匹配情况，true/false。
dp的初始化需要考虑空串 ，s为空 or p为空。
-
初始化，i = 0 时，p[0..i-1]为空串，仅能与空串(j = 0)匹配成功
dp[0][0] = true; -
初始化，j = 0 时，s[0..j-1]为空串，仅能与空串(i = 0)或'...'匹配成功
当p[0..i-1]是连续的'*'时，dp[i][0] = true; -
i = [1..p.length()]，遍历p[0..p.length()-1]，逐行推导
j = [1..s.length()]，遍历s[0..s.length()-1]-
若p[i-1] == '*'，可不匹配字符，或匹配字符
dp[i][j] = dp[i-1][j] || dp[i][j-1] -
若p[i-1] == '?'，匹配字符
dp[i][j] = dp[i-1][j-1] -
若p[i-1] == 字母，与s[j-1]比较，相等就匹配成功，不等就匹配失败
dp[i][j] = dp[i-1][j-1] && p[i-1] == s[j-1]
-
实现
dp数组的推导公式可知，dp[i]仅与dp[i-1]有关，可以压缩二维dp数组为一维，注意j=0时的dp值
class Solution {
public:
bool isMatch(string s, string p) {
const int sLen = s.length(), pLen = p.length();
vector<bool> dpLine(sLen + 1, false);
dpLine[0] = true;
int dpZeroTrue = 1;
for(; dpZeroTrue <= pLen && p[dpZeroTrue - 1] == '*'; ++dpZeroTrue);
// 字符串i-1对应dpi，字符串j-1对应dpj
for(int i = 1; i <= pLen; ++i) {
const char pi = p[i - 1];
if(pi == '*') {
dpLine[0] = i < dpZeroTrue;
for(int j = 1; j <= sLen; ++j) {
dpLine[j] = dpLine[j - 1] || dpLine[j];
}
} else if(pi == '?'){
for(int j = sLen; j > 0; --j) {
dpLine[j] = dpLine[j - 1];
}
dpLine[0] = i < dpZeroTrue;
} else {
for(int j = sLen; j > 0; --j) {
dpLine[j] = dpLine[j - 1] && pi == s[j - 1];
}
dpLine[0] = i < dpZeroTrue;
}
}
return dpLine.back();
}
};