# JAVA DP solution

• ``````    public class Solution {
public int[][] table;
public int minDistance(String word1, String word2) {
if(word2.length()==0) return word1.length();
if(word1.length()==0) return word2.length();
table=initialTable(word1.length(),word2.length());
return findMin(word1, word2, 0,0,word1.length());
}

int findMin(String word1, String word2, int x1, int x2,int l1){
if(x1==word1.length()) return word2.length()-l1;
if(x2==word2.length()) return l1-x2;
if(table[x1][x2]==-1){
int count=0;
if(word1.charAt(x1)==word2.charAt(x2)){
count=findMin(word1,word2,x1+1,x2+1,l1);
}else{
//not equal
int countInsert=1+findMin(word1,word2,x1,x2+1,l1+1);
int countDel=1+findMin(word1,word2,x1+1,x2,l1-1);
int countRlc=1+findMin(word1,word2,x1+1,x2+1,l1);
count=min(countInsert,countDel,countRlc);
}

table[x1][x2]=count;
}
return table[x1][x2];
}

int min(int a,int b,int c){
int tmpMin=Math.min(a,b);
tmpMin=Math.min(tmpMin,c);
return tmpMin;
}

int[][] initialTable(int l1,int l2){
int[][] table=new int[l1][l2];
for(int i=0;i<l1;i++){
for(int j=0; j<l2;j++){
table[i][j]=-1;
}
}
return table;
}
}
``````

Hope this is easy to understand.
Basically consider all the case, pretend that we insert/replace/delete word1 by only changing its expected length. And count the num of operations.
Then use a table to store the intermediate results

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