Solution explaining how to approach the DP solution from a recurrence pattern in Java


  • 0
    L

    The first rule of DP is to establish a recurrence relationship so that no guess work is involved with the E-table. If you have done Levenshtein Distance (Edit distance) algo before, here is the quick thought on using recursion:

    private int helper(String s1, String s2,int i, int j) {
            if(i==s1.length()) {
                return s2.length()-j;
            }
            else if(j==s2.length()) {
                return s1.length()-i;
            }
            
            if(s1.charAt(i)==s2.charAt(j)) {
                return helper(s1,s2,i+1,j+1);
            }
            else {
                return 1+Math.min(helper(s1,s2,i+1,j),helper(s1,s2,i,j+1));
            }
            
        }
    

    However, as expected, it will time out :). Now, the idea is to leverage the above and using a top-bottom memoization-based DP to cache the results for reuse. Here is the code for that:

     public int minDistance(String word1, String word2) {
            int[][] dp = new int[word1.length()+1][word2.length()+1];
            for(int[] r : dp) {
                Arrays.fill(r,-1);
            }
            return helper_dp(word1,word2,0,0,dp);
        }
        private int helper_dp(String s1, String s2,int i, int j,int[][] dp) {
            if(i==s1.length()) {
                return s2.length()-j;
            }
            else if(j==s2.length()) {
                return s1.length()-i;
            }
            
            if(s1.charAt(i)==s2.charAt(j)) {
                if(dp[i][j]==-1) {
                    dp[i][j] = helper_dp(s1,s2,i+1,j+1,dp);
                }
                return dp[i][j];
            }
            else {
                if(dp[i+1][j]==-1) {
                    dp[i+1][j] = helper_dp(s1,s2,i+1,j,dp);
                }
                if(dp[i][j+1]==-1) {
                    dp[i][j+1] = helper_dp(s1,s2,i,j+1,dp);
                }
                return 1+Math.min(dp[i+1][j],dp[i][j+1]);
            }
            
        }    
        
    

Log in to reply
 

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