# Simple java solution implement algorithm from text book

E(i,j) = min{1+E(i-1,j),1+E(i,j-1),diff(i,j)+E(i-1,j-1)}

The solution is enhanced with cache so it can be accepted without TLE

``````public class Solution {

public int minDistance(String word1, String word2) {

if(word1.length() ==0 && word2.length() !=0)
{
return word2.length();
}
if(word1.length()!=0 && word2.length() ==0)
{
return word1.length();
}
int[][] mem = new int[word1.length()][word2.length()];
for(int[] row : mem) Arrays.fill(row,-1);
return editdistance(word1,word1.length()-1,word2,word2.length()-1,mem);
}
public int editdistance(String word1,int i,String word2,int j,int[][] mem)
{
if(i ==-1 && j == -1) return 0;
if(j == -1) return i+1;
if(i == -1) return j+1;
if(mem[i][j]!=-1) return mem[i][j];
int a = 1+editdistance(word1,i-1,word2,j,mem);
int b = 1+editdistance(word1,i,word2,j-1,mem);
int c = word1.charAt(i)==word2.charAt(j)?editdistance(word1,i-1,word2,j-1,mem):1+editdistance(word1,i-1,word2,j-1,mem);
int minDistance = Math.min(a,Math.min(b,c));
mem[i][j] = minDistance;
return minDistance;
}
``````

}

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