# Easy to understand recursive/DP solution, beats 99.6%

• public class Solution {
int[][] dp;

public int minDistance(String word1, String word2) {
dp = new int[word1.length()][word2.length()];

return minDistanceHelper(word1, word2, 0, 0);
}

private int minDistanceHelper(String word1, String word2, int index1, int index2) {
if (index1 == word1.length()) return word2.length() - index2;
if (index2 == word2.length()) return word1.length() - index1;

if (dp[index1][index2] > 0) return dp[index1][index2];

int result;
if (word1.charAt(index1) == word2.charAt(index2)) {
result = minDistanceHelper(word1, word2, index1+1, index2+1);
} else {
// replace char
result = 1 + minDistanceHelper(word1, word2, index1+1, index2+1);

// delete char from word1
result = Math.min(result, 1 + minDistanceHelper(word1, word2, index1+1, index2));

// delete char from word2
result = Math.min(result, 1 + minDistanceHelper(word1, word2, index1, index2+1));
}

dp[index1][index2] = result;
return result;
}
}

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