package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/edit-distance/
 */
public class Problem72 {
    public int minDistance(String word1, String word2) {
        Map<String, Integer> memo = new HashMap<>();
        return minDistance(word1, word2, word1.length(), word2.length(), memo);
    }

    private int minDistance(String word1, String word2, int i, int j, Map<String, Integer> memo) {
        String key = i + "|" + j;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        if (i == 0) {
            return j;
        }
        if (j == 0) {
            return i;
        }
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            return minDistance(word1, word2, i - 1, j - 1, memo);
        }
        // insert
        int a = minDistance(word1, word2, i, j - 1, memo);
        // delete
        int b = minDistance(word1, word2, i - 1, j, memo);
        // replace
        int c = minDistance(word1, word2, i - 1, j - 1, memo);
        int min = 1 + Math.min(a, Math.min(b, c));
        memo.put(key, min);
        return min;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -157,36 +157,24 @@
 %0A       
- Map%3CString,
  Integer
 %3E memo =
@@ -161,25 +161,28 @@
      Integer
-%3E
+%5B%5D%5B%5D
  memo = new 
@@ -185,19 +185,55 @@
 new 
-HashMap%3C%3E()
+Integer%5Bword1.length() + 1%5D%5Bword2.length() + 1%5D
 ;%0A  
@@ -390,28 +390,16 @@
 t j,
- Map%3CString,
  Integer
 %3E me
@@ -398,9 +398,12 @@
 eger
-%3E
+%5B%5D%5B%5D
  mem
@@ -419,67 +419,30 @@
     
-String key = i + %22%7C%22 + j;%0A        if (memo.containsKey(key)
+if (memo%5Bi%5D%5Bj%5D != null
 ) %7B%0A
@@ -468,17 +468,14 @@
 memo
-.get(key)
+%5Bi%5D%5Bj%5D
 ;%0A  
@@ -1027,22 +1027,20 @@
 memo
-.put(key,
+%5Bi%5D%5Bj%5D =
  min
-)
 ;%0A  

Update problem 72