@@ -0,0 +1,1413 @@
+package com.be1ive.leetcode;%0A%0A/**%0A * https://oj.leetcode.com/problems/edit-distance/%0A */%0Apublic class EditDistance %7B%0A%0A    // to make word2 from word1%0A    //  dp%5Bi%5D%5Bj%5D edit distance of %5BT%5B0%5D..T%5Bi%5D%5D and %5BS%5B0%5D..S%5Bj%5D%5D%0A    //  T%5B0%5D == %22%22 =%3E dp%5B0%5D%5Bj%5D = j%0A    //  S%5B0%5D == %22%22 =%3E dp%5Bi%5D%5B0%5D = i%0A    //%0A    //  dp%5Bi%5D%5Bj%5D = (S%5Bi%5D == T%5Bj%5D) ? dp%5Bi - 1%5D%5Bj - 1%5D - nothing%0A    //                            : min(dp%5Bi - 1%5D%5Bj%5D - insert, dp%5Bi%5D%5Bj - 1%5D - delete, dp%5Bi - 1%5D%5Bj - 1%5D - replace)%0A    public int minDistance(String word1, String word2) %7B%0A        if (!word1.isEmpty() && !word2.isEmpty()) %7B%0A            int n = word1.length();%0A            int m = word2.length();%0A%0A%0A            int%5B%5D%5B%5D dp = new int%5Bn + 1%5D%5Bm + 1%5D;%0A%0A            for (int i = 1; i %3C= n; i++) %7B%0A                dp%5Bi%5D%5B0%5D = i;%0A            %7D%0A%0A            for (int j = 1; j %3C= m; j++) %7B%0A                dp%5B0%5D%5Bj%5D = j;%0A            %7D%0A%0A            for (int i = 1; i %3C= n; i++) %7B%0A                for (int j = 1; j %3C= m; j++) %7B%0A                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) %7B%0A                        dp%5Bi%5D%5Bj%5D = dp%5Bi - 1%5D%5Bj - 1%5D;%0A                    %7D else %7B%0A                        dp%5Bi%5D%5Bj%5D = Math.min(Math.min(dp%5Bi - 1%5D%5Bj%5D + 1, dp%5Bi%5D%5Bj - 1%5D + 1), dp%5Bi - 1%5D%5Bj - 1%5D + 1);%0A                    %7D%0A                %7D%0A            %7D%0A%0A            return dp%5Bn%5D%5Bm%5D;%0A%0A        %7D else %7B%0A            return Math.max(word1.length(), word2.length());%0A        %7D%0A    %7D%0A%0A%7D%0A

Edit Distance