44. 通配符匹配

44. 通配符匹配

类似剑指 Offer 19. 正则表达式匹配 | Cinte's Leetcode Record

dp

class Solution {
public:
    bool isMatch(string s, string p) {
        int length1 = s.size(), length2 = p.size();
        vector<vector<int>> dp(length1 + 1, vector<int>(length2 + 1, false));
        dp.back().back() = true;
        for(int i = length1; i >= 0; --i)
        {
            for(int j = length2 - 1; j >= 0; --j)
            {
                bool firstMatch = i < length1 && (s[i] == p[j] || p[j] == '?');
                if(p[j] == '*')
                    dp[i][j] = dp[i][j + 1] || (i < length1 && dp[i + 1][j]); // 如果我匹配你星号，那我要看看我前面的串能不能和你匹配。如果我拒绝你的星号，那我要看看我能不能和你前面的表达式匹配
                else if(i < length1)
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
        return dp[0][0];
    }
};