博客

题目：

给定一个字符串 (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()];
    }
};