1 public class Solution {
 2     public int minDistance(String word1, String word2) {
 3         int len1 = word1.length();
 4         int len2 = word2.length();
 5         int dp[][] = new int[len1+1][len2+1];
 6         for(int i=0;i<=len1;i++){
 7             for(int j=0;j<=len2;j++){
 8                 if(i==0){
 9                     dp[i][j]=j;
10                 }
11                 else if(j==0){
12                     dp[i][j]=i;
13                 }
14                 else if(word1.charAt(i-1)==word2.charAt(j-1)){
15                     dp[i][j] = dp[i-1][j-1];
16                 }
17                 else{
18                     dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
19                 }
20             }
21         }
22         return dp[len1][len2];
23     }
24 }