public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
if (len1 == 0) return len2;
if (len2 == 0) return len1;
// dp[i][j] stands for distance of first i chars of word1 and first j chars of word2
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++)
dp[i][0] = i;
for (int j = 0; j <= len2; j++)
dp[0][j] = j;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i  1) == word2.charAt(j  1))
dp[i][j] = dp[i  1][j  1];
else
dp[i][j] = Math.min(Math.min(dp[i  1][j  1] + 2, dp[i  1][j] + 1), dp[i][j  1] + 1);
}
}
return dp[len1][len2];
}
}
Java DP Solution, same as Edit Distance


@shawngao I wonder whether
dp[i1][j1]+2
could be ignored ? It seems likedp[i1][j1]+2>=max{dp[i1][j]+1, dp[i][j1]+1}
(although I don't know why), so thatdp[i1][j1]+2
will never be the smallest one.

said in Java DP Solution, same as Edit Distance:
else
dp[i][j] = Math.min(Math.min(dp[i  1][j  1] + 2, dp[i  1][j] + 1), dp[i][j  1] + 1);The only difference part comparing with "Edit Distance". Else are same.
in Edit Distance is(I start i,j from 0, end (< word1.Length, <word2.Length)
else { dp[i+1, j + 1] = Math.Min(Math.Min(dp[i,j+1],dp[i+1,j]), dp[i,j]) + 1; }
In here, it's
else { dp[i+1, j + 1] = Math.Min(Math.Min(dp[i,j+1], dp[i,j]+1), dp[i+1,j]) +1; }


Reduce space to O(n). C++ version.
class Solution { public: int minDistance(string word1, string word2) { size_t m = word1.length(), n = word2.length(); vector<int>f(n+1,0); for(size_t j=0; j<=n; j++) f[j] = j; for(size_t i=1; i<=m; i++) { int prev = f[0]; f[0] = i; for(size_t j=1; j<=n; j++) { int save = f[j]; if(word1[i1]==word2[j1]) f[j] = prev; else f[j] = min(prev+2, min(f[j]+1, f[j1]+1)); prev = save; } } return f[n]; } };

@shawngao said in Java DP Solution, same as Edit Distance:
Math.min(Math.min(dp[i  1][j  1] + 2, dp[i  1][j] + 1), dp[i][j  1] + 1);
Nice solution. Since we're permitted to operate only one character at a time, checking to delete both characters is not required, although it produces same result since you add 2.
dp[i][j] = Math.min(dp[i  1][j], dp[i][j  1]) + 1;