leetcode 困难 —— 通配符匹配（简单dp）_dp表解决通配符

题目：
给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘’ 的通配符匹配。
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

题解：
字符串匹配问题，一般都是 dp 解决，dp[i][j] 为 s 的前 i 个字符 和 p 的前 j 个字符，太典了
思考一下状态是如何转移的
如果 s 的第 i 个字符和 p 的第 j 个字符相同，或 p 的第 j 个为 ‘?’，则 dp[i][j] = dp[i-1][j-1]
如果 s 的第 i 个字符和 p 的第 j 个字符不相同，则 dp[i][j] = false
如果 p 的第 j 个字符为 ‘*’，则 dp[i % 2][j] = dp[(i - 1) % 2][j - 1] || dp[i % 2][j - 1] || dp[(i - 1) % 2][j];
（对应三种 * 变化情况）

然后注意预处理数组的时候，当 “” 和 “****” 是匹配的即可，即 dp[0][4] = true

由于没有给数据范围，所以怕两个字符太大，压成一个二维的
但是此时需要注意，dp[0][0] 这个可能会影响后面的数据，把之后的 dp[i][0] 需注意设为 1

class Solution {
public:
    bool dp[2][1035];
    bool isMatch(string s, string p) {    
        dp[0][0] = true;
        int f = 1;
        while(f <= p.size() && p[f - 1] == '*') {
            dp[0][f] = true;
            f++;
        }
        for(int i = 1; i <= s.size(); i++) {
            dp[i % 2][0] = false;
            for(int j = 1; j <= p.size(); j++) {
                if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
                }
                else if(p[j - 1] == '*') {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] || dp[i % 2][j - 1] || dp[(i - 1) % 2][j];
                }
                else {
                    dp[i % 2][j] = false;
                }
            }
        }
        return dp[s.size() % 2][p.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27