dynamic programming
a1...n > b1...m have three ways

a1...n1 > b1...m, delete an => distance[i+1][j+1] = distance[i][j+1] + 1

a1...n > b1...m1, delete bm => distance[i+1][j+1] = distance[i+1][j] + 1

a1..n1 > b1...m1, replace an1 to bm1 => distance[i+1][j+1] = distance[i][j] + cost
cost = a[i]==b[j]?0:1
public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] distance = new int[m+1][n+1];
for (int i=0;i<=n;i++) {
distance[0][i] = i;
}
for (int i=0;i<=m;i++) {
distance[i][0] = i;
}
for (int i=0;i<m;i++) {
for (int j=0;j<n;j++) {
int cost = word1.charAt(i)==word2.charAt(j)?0:1;
int minValue = Math.min(distance[i+1][j],distance[i][j+1]);
distance[i+1][j+1] = distance[i][j]<=minValue?distance[i][j]+cost:minValue+1;
}
}
return distance[m][n];
}
}