Top down O(MN) DP Java


  • 0
    A
    class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();
            boolean [][] dp = new boolean[m + 1][n + 1];
            //dp[i][j] means s[0, i] matches p[0, i]
            dp[0][0] = true; //Empty
            for(int k = 1; k <= n; ++k){
               if(p.charAt(k - 1) == '*' && k - 2 >= 0){
                   dp[0][k] = dp[0][k - 2];
               } 
            }
            for(int i = 1; i <= m; ++i){
                for(int j = 1; j <= n; ++j){
                    if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'){
                        dp[i][j] = dp[i - 1][j - 1];
                    } 
                    
                    else if(p.charAt(j - 1) == '*' ){
                        char prev = p.charAt(j - 2);
                        dp[i][j] =  dp[i][j - 2] || (dp[i - 1][j] && (prev == '.' || prev == s.charAt(i - 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.