Java solution DP with detailed explanation


  • 0
    M

    Every time you see a DP problem, you should first derive the objective function.

    Here is the definition of our objective function:

    dp[i][j] = true if s[1..i] and p[1..j] matches
    

    Let's start our derivation! First of all, we will divide the problem into three categories:

    * p[j] = '.'
    dp[i][j] = dp[i-1][j-1] since p[j] can match any s[i]
    
    * p[j] = '*'
      * in case of dp[i][j-2] is true, p[j] can used as empty character 
      * in case of dp[i-1][j] is true, p[j] is used to match one or more characters. 
        - p[j-1] == s[i]
        - p[j-1] == '.'
    
    * list itemp[j] = a-zA-Z
    if dp[i-1][j-1] is true, it means that s[1..i-1] can match p[1..j-1]. we only have to check whether s[i] match p[j]
    
    
    class Solution {
        public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[s.length()+1][p.length()+1];
            dp[0][0] = true;
            
            for (int j = 2; j <= p.length(); j++) {
                if (p.charAt(j-1) == '*' && dp[0][j-2]) {
                    dp[0][j] = true;
                }
            }        
            
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= p.length(); j++) {
                    if (p.charAt(j-1) == '.') {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    
                    if (p.charAt(j-1) == '*') {
                        dp[i][j] = dp[i][j-2]  || dp[i-1][j] && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.');
                    }
                    
                    if (s.charAt(i-1) == p.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
            
            return dp[s.length()][p.length()];
        }
    }
    

Log in to reply
 

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