class Solution {
private int [][]dp;
private char [] s1;
private char [] s2;
public int minDistance(String word1, String word2) {
s1=word1.toCharArray();
s2=word2.toCharArray();
dp=new int[s1.length][s2.length];
for(int [] item:dp)
{
Arrays.fill(item, -1);
}
return rec(s1.length-1,s2.length-1);
}
private int rec(int i, int j) {
// TODO Auto-generated method stub
if(j==-1)
return i+1;
if(i==-1)
return j+1;
if(dp[i][j]!=-1)
return dp[i][j];
if(s1[i]==s2[j])
{
dp[i][j]=rec(i-1,j-1);
}
else
{
dp[i][j]=1+min(rec(i-1,j),rec(i-1,j-1),rec(i,j-1));
}
return dp[i][j];
}
private int min(int rec, int rec2, int rec3) {
// TODO Auto-generated method stub
return Math.min(rec, Math.min(rec2, rec3));
}
}
