package leetcode;

/**
 * https://leetcode.com/problems/edit-distance/
 */
public class Problem72 {
    public int minDistance(String word1, String word2) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem72 prob = new Problem72();
        System.out.println(prob.minDistance("geek", "gesek")); // 1
        System.out.println(prob.minDistance("cat", "cut")); // 1
        System.out.println(prob.minDistance("sunday", "saturday")); // 3
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -211,333 +211,930 @@
     
-// TODO%0A        return 0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem72 prob = new Problem72();%0A        System.out.println(prob.minDistance(%22geek%22, %22gesek%22)); // 1%0A        System.out.println(prob.minDistance(%22cat%22, %22cut%22)); // 1%0A        System.out.println(prob.minDistance(%22sunday%22, %22saturday%22)); // 3
+Map%3CString, Integer%3E memo = new HashMap%3C%3E();%0A        return minDistance(word1, word2, word1.length(), word2.length(), memo);%0A    %7D%0A%0A    private int minDistance(String word1, String word2, int i, int j, Map%3CString, Integer%3E memo) %7B%0A        String key = i + %22%7C%22 + j;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        if (i == 0) %7B%0A            return j;%0A        %7D%0A        if (j == 0) %7B%0A            return i;%0A        %7D%0A        if (word1.charAt(i - 1) == word2.charAt(j - 1)) %7B%0A            return minDistance(word1, word2, i - 1, j - 1, memo);%0A        %7D%0A        // insert%0A        int a = minDistance(word1, word2, i, j - 1, memo);%0A        // delete%0A        int b = minDistance(word1, word2, i - 1, j, memo);%0A        // replace%0A        int c = minDistance(word1, word2, i - 1, j - 1, memo);%0A        int min = 1 + Math.min(a, Math.min(b, c));%0A        memo.put(key, min);%0A        return min;
 %0A   

Solve problem 72