C++ DP 7 lines


  • 1
    V
    bool isMatch(string s, string p) {
        bool dp[s.size() + 1][p.size() + 1] = {};
        dp[0][0] = true;
        for (auto i = 0; i <= s.size(); ++i)
        for (auto j = 1; j <= p.size(); ++j) {
            if (p[j - 1] == '*') dp[i][j] = dp[i][j - 2] || (i > 0 && dp[i - 1][j] && (p[j - 2] == '.' || p[j - 2] == s[i - 1]));
            else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (p[j - 1] == '.' || p[j - 1] == s[i - 1]); 
        }
        return dp[s.size()][p.size()];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.