Java Solution, visualized in comments to explain how the edits work


  • 0
    A
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            
            // DP table: min edits it takes to convert first i chars of word1 -> to first j chars of word2
            //    _ a b c d e f
            // _  0 1 2 3 4 5 6
            // b  1 1 2 3 4 5 6 "b" -> "a", "b" -> "ab", "b" -> "abc", "b" -> "abcd"...
            // c  2             "cb" -> "a", "cb" -> "ab", "cb" -> "abc"....
            // e  3
            // f  4             "bcef" -> "a", "bcef" -> "ab", ..."bcef" -> "abcdef"
            // Comparing j-col word B to achieve i-row word A, action on B
            int[][] edits = new int[m + 1][n + 1];
            
            // first row/col, # edits to create word from scratch ""; num edits = # char
            for (int i = 0; i <= m; i++) {
                edits[i][0] = i;
            }
            for (int j = 0; j <= n; j++) {
                edits[0][j] = j;
            }
            
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (word1.charAt(i-1) == word2.charAt(j-1)) {
                        // no edits needed; "abcd" -> "abcde" = "bc" -> "bce" same as prev state A, B adding same char
                        edits[i][j] = edits[i-1][j-1];
                    } else {
                        // same as achieving the prev str state, "abcd" vs "bce" insert e onto B only, but using 1 more
                        // op to achieve it
                        int add = edits[i][j-1] + 1;
                        // same as achieving the prev str state, "abcde" vs "bc" del e on B, but using 1 more op to achieve it
                        int del = edits[i-1][j] + 1;
                        // same as prev A, B add 1 char to both, replace: "abc" -> "abcd" = "bc" -> "bcD"
                        int replace = edits[i-1][j-1] + 1;
                        
                        int min = Math.min(add, del);
                        min = Math.min(min, replace);
                        
                        edits[i][j] = min;  // take min of compare all 3 possible changes, to achieve curr state
                    }
                }
            }
            return edits[m][n];
        }

Log in to reply
 

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