44. Wildcard Matching

问题：

正则表达中，给定匹配对象s，和模式串p，问是否匹配。

其中，* 可匹配任意长度字串，? 可匹配一个单位长度的字串。

Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:
Input: s = "mississippi", p = "mis*is*p*."
Output: false
 
Constraints:
0 <= s.length <= 20
0 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

解法：DP（动态规划）Backtracking（回溯算法）

一，回溯算法：（不推荐）

对于本问题，两个变量：

路径：到目前为止匹配到的位置s[sp], p[pp]
选择列表：下一次匹配的可能：
- 字母相同 or 模式串匹配到? or 模式串匹配到*：sp+1，pp+1
- 模式串匹配到*：sp，pp+1 或者 sp+1，pp

处理过程:

base：递归退出条件：
- sp和pp都匹配到最后一位。res=true，匹配成功
- 只有pp匹配到最后一位，匹配失败
- 只有sp匹配到最后一位，若pp只剩下*，那么匹配成功，否则匹配失败
做选择：对于当前位置，选择其中一个可用数字a。
- sp+1, pp+1 或者 sp不变，pp+1 或者 sp+1，pp不变
撤销选择：回退到选择数字a之前的状况。
- sp，pp

⚠️ 注意：本题使用回溯还是会超时，即使使用 preDeleteMultX 将连续多个*转为一个*

代码参考：

 1 class Solution {
 2 public:
 3     void backtrack(bool& res, string s, string p, int sp, int pp) {
 4         if(sp == s.size() && pp == p.size()) {
 5             res = true;
 6             return;
 7         } else if(pp == p.size()) {
 8             return;
 9         } else if(sp == s.size()) {
10             if(p[pp] == '*') {
11                 backtrack(res, s, p, sp, pp+1);
12                 if(res) return;
13             }
14             return;
15         }
16         if(s[sp] == p[pp] || p[pp] == '?' || p[pp] == '*') {
17             backtrack(res, s, p, sp+1, pp+1);
18         }
19         if(res) return;
20         if(p[pp] == '*') {
21             backtrack(res, s, p, sp, pp+1);
22             if(res) return;
23             backtrack(res, s, p, sp+1, pp);
24             if(res) return;
25         }
26         return;
27     }
28     void preDeleteMultX(string& p) {
29         int pos = 0;
30         while(pos<p.size()) {
31             if(p[pos]=='*') {
32                 pos++;
33                 while(pos<p.size() && p[pos]=='*') {
34                     p.erase(p.begin()+pos);
35                 }
36             }else{
37                 pos++;
38             }
39         }
40     }
41     bool isMatch(string s, string p) {
42         bool res = false;
43         preDeleteMultX(p);
44         backtrack(res, s, p, 0, 0);
45         return res;
46     }
47 };

二，DP

1.确定【状态】：

字符串s的第i个字符：s[i]
匹配串第j个字符：p[j]

2.确定【选择】：dp[i][j] 分4种情况

s[i] == p[j] 或者 p[j] == '?' ：该字符匹配上
- 前一个子串状态: =dp[i-1][j-1]
p[j] == '*'：该字符可能匹配上"*"
- 匹配当前s[i]，则又分为以下三种"*"的匹配情况，他们之间求OR：
  - 匹配0次（匹配串的 j 跳过一个字符*，字符串的 i 跳过0个字符）：=dp[i][j-1]
  - 匹配1次（匹配串的 j 跳过一个字符*，字符串的 i 跳过一个字符）：=dp[i-1][j-1]
  - 匹配>1次（匹配串的 j 跳过0个字符，字符串的 i 跳过一个字符）：=dp[i-1][j]
该字符未匹配
- false

3. dp[i][j]的含义：

字符串s的0～第 i 个字符，是否能被匹配串p的0～第 j 个字符，匹配上。

4. 状态转移：

dp[i][j]=

(s[i] == p[j] 或者 p[j] == '.' )：=前一个子串状态：dp[i-1][j-1]
(p[j] == '*')：
- 前一个字符匹配s当前字符，OR {
  - 使*匹配0次：dp[i][j-1]
  - 使*匹配1次：dp[i-1][j-1]
  - 使*匹配>1次：dp[i-1][j] }
其他则不匹配：=false

5. base case：

dp[i][0]=false：任意字符串s，匹配空串，除非空串自己，其他都为false。
- dp[0][0]=true
dp[0][j]=true：当dp[0][j-1]==true && p[j]=='*'
- "***...*"只有这种情况能匹配任意空串字符串s。

代码参考：

 1 class Solution {
 2     //dp[i][j]:s[0-i],p[0-j] ismatch?
 3     //case_1: s[i]==p[j] ==dp[i-1][j-1]
 4     //case_2: p[j]=='?' ==dp[i-1][j-1]
 5     //case_3: p[j]=='*' ==dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j]
 6     //base_case: dp[0][0]=true, dp[0][j]=(dp[0][j-1]&&p[j]==*), dp[i][0]=false
 7 public:
 8     bool isMatch(string s, string p) {
 9         int sn = s.size();
10         int pn = p.size();
11         if(sn==0 && pn==0) return true;
12         if(pn==0) return false;
13         vector<vector<bool>> dp(sn+1, vector<bool>(pn+1, false));
14         //base:
15         dp[0][0] = true;
16         for(int j=1; j<=pn; j++) dp[0][j] = (dp[0][j-1]&&p[j-1]=='*');
17         if(sn>=1) dp[1][0] = false;
18         for(int i=1; i<=sn; i++) {
19             for(int j=1; j<=pn; j++) {
20                 if(s[i-1]==p[j-1] || p[j-1]=='?'){
21                     dp[i][j] = dp[i-1][j-1];
22                 } else if(p[j-1]=='*') {
23                     dp[i][j] = (dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j]);
24                 }
25             }
26         }
27         
28         return dp[sn][pn];
29     }
30 };

6. ♻️ 优化：降维打击

⚠️ 注意，由于5中初始化所有可能为false，

而在6降维打击后，每次使用的cell为上一层遍历残留数据，因此对【两个字符不相同】的情况，需要赋值false。

 1 class Solution {
 2     //dp[i][j]:s[0-i],p[0-j] ismatch?
 3     //case_1: s[i]==p[j] ==dp[i-1][j-1]
 4     //case_2: p[j]=='?' ==dp[i-1][j-1]
 5     //case_3: p[j]=='*' ==dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j]
 6     //case_4: s[i]!=p[j] ==false
 7     //base_case: dp[0][0]=true, dp[0][j]=(dp[0][j-1]&&p[j]==*), dp[i][0]=false
 8 public:
 9     bool isMatch(string s, string p) {
10         int sn = s.size();
11         int pn = p.size();
12         if(sn==0 && pn==0) return true;
13         if(pn==0) return false;
14         vector<bool>dp(pn+1, false);
15         //base:
16         dp[0] = true;
17         for(int j=1; j<=pn; j++) dp[j] = (dp[j-1]&&p[j-1]=='*');
18         //if(sn>=1) dp[0] = false;
19         bool tmp;
20         bool memo;
21         for(int i=1; i<=sn; i++) {
22             tmp = dp[0];
23             dp[0]=false;
24             for(int j=1; j<=pn; j++) {
25                 memo = dp[j];
26                 if(s[i-1]==p[j-1] || p[j-1]=='?'){
27                     dp[j] = tmp;
28                 } else if(p[j-1]=='*') {
29                     dp[j] = (tmp || dp[j-1] || dp[j]);
30                 } else {
31                     dp[j] = false;
32                 }
33                 tmp = memo;
34             }
35         }
36         
37         return dp[pn];
38     }
39 };