0072-edit-distance.java

//Refer to neetcode's video

//Memoized code

classSolution {

publicintminDistance(Stringword1, Stringword2) {
intm = word1.length() - 1;
intn = word2.length() - 1;
int[][] dp = newint[m + 2][n + 2];
for (int[] d : dp) {
Arrays.fill(d, -1);
 }
returnhelper(word1, word2, m, n, dp);
 }

publicinthelper(Stringword1, Stringword2, intm, intn, int[][] dp) {
//the strings are null
if (m + 1 == 0 && n + 1 == 0) {
return0;
 }
//one of the strings are null
if (m + 1 == 0 || n + 1 == 0) {
returnMath.max(m + 1, n + 1);
 }
//both values at the index are equal
if (dp[m][n] != -1) returndp[m][n];
if (word1.charAt(m) == word2.charAt(n)) {
dp[m][n] = helper(word1, word2, m - 1, n - 1, dp);
returndp[m][n];
 } else {
//try deletion
intdelete = 1 + helper(word1, word2, m - 1, n, dp);
//try insertion
intinsert = 1 + helper(word1, word2, m, n - 1, dp);
//try replacing
intreplace = 1 + helper(word1, word2, m - 1, n - 1, dp);
//now we'll choose the minimum out of these 3 and add 1 for the operation cost
dp[m][n] = Math.min(Math.min(delete, insert), replace);
returndp[m][n];
 }
 }
}