Intuitive Java DP Solution with Explanations and Examples


  • 0
    C
        // O(n^2) time, O(n^2) space
        // can be optimized with O(n) space --> only keep one row because we only need the previous row to update the current row
        public int minDistance(String word1, String word2) {
            if (word1 == null || word2 == null) return -1;
            if (word1.length() == 0) return word2.length();
            if (word2.length() == 0) return word1.length();
            
            int l1 = word1.length();
            int l2 = word2.length();
            
            // minDist[i][j] represents the min distance between the substring(0, i) of word1 and the substring(0, j) of word2
            int[][] minDist = new int[l1][l2];
            
            // initialize
            minDist[0][0] = word1.charAt(0) == word2.charAt(0) ? 0 : 1;
            for (int i = 1; i < l1; i++) {
                if (minDist[i - 1][0] != i || word1.charAt(i) == word2.charAt(0)) {
                    minDist[i][0] = i;
                } else{
                    minDist[i][0] = i + 1;
                }
            }
            for (int i = 1; i < l2; i++) {
                if (minDist[0][i - 1] != i || word2.charAt(i) == word1.charAt(0)) {
                    minDist[0][i] = i;
                } else{
                    minDist[0][i] = i + 1;
                }
            }
            
            // DP
            for (int i = 1; i < l1; i++) {
                for (int j = 1; j < l2; j++) { 
                    // eg. The distance between "ABCE" and "BDE" is the same as distance between "AB" and "BD"
                    if (word1.charAt(i) == word2.charAt(j)) {
                        minDist[i][j] = minDist[i - 1][j - 1];
                    } else {
                    // The min distance from s1 to s2 is either:     eg. s1="ABCE", s2="BDF"
                    // deletion:   min[i-1][j] + 1                      1 + "ABC"- > "BDF" (1 represents deleting 'E' from "ABCE")
                    // insertion:    min [i] [j-1] + 1                  1 + "ABCE" -> "BD"
                    //                                                  insert 'F' to s1 is equivalent to delete 'F' from s2
                    // replacement: min[i-1][j-1] + 1
                        minDist[i][j] = Math.min(Math.min(minDist[i - 1][j], minDist[i][j - 1]), minDist[i - 1][j - 1]) + 1;
                    }
                }
            }
            
            return minDist[l1 - 1][l2 - 1];
    

Log in to reply
 

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