Simple Java DP Solution


  • 0

    The idea is closely based on the edit distance problem,
    where you end up building the dp array with the following equation:
    dp[i][j] represent the solution for the subproblem word1(1..i) and word2(1..j)
    dp[i][j] = dp[i-1][j-1] if the word1[i] == word2[j]
    = 1 + Math.min(dp[i-1][j], dp[i][j-1]), if not equal

    public static int minDistance(String word1, String word2) {
            int len1 = word1.length()+1, len2 = word2.length()+1;
            int[][] dp = new int[len1][len2];
    
            for(int i = 0; i < len1; i++) {
                for(int j = 0; j < len2; j++) {
                    if(i == 0 && j == 0) dp[i][j] = 0;
                    else if(i == 0) dp[i][j] = 1 + dp[i][j-1];
                    else if(j == 0) dp[i][j] = 1 + dp[i-1][j];
                    else if(word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                    else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]);
                }
            }
            return dp[len1-1][len2-1];
        }
    

Log in to reply
 

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