C++, simple, short, DP solution, O(MN) time, O(MN) space


  • 0
    C
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.size();
            int n = p.size();
            //dp[i][j] : true: s of length i matches p of length of j.
            vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
            
            dp[0][0] = true;
            for (int i = 0; i <= m; i++)
                for (int j = 1; j <= n; j++)
                {
                    if (p[j-1] == '*')
                        //not match '*' or match '*'
                        dp[i][j] = (i > 0 && dp[i-1][j]) || dp[i][j-1];
                    else
                        dp[i][j] = (i > 0) && (s[i-1] == p[j-1] || p[j-1] == '?') && dp[i-1][j-1];
                }
            return dp[m][n];      
        }
    };

Log in to reply
 

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