# Java DP Solution, same as Edit Distance

• ``````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];
}
}
``````

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

• 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[i-1]==word2[j-1]) f[j] = prev;
else f[j] = min(prev+2, min(f[j]+1, f[j-1]+1));
prev = save;
}
}
return f[n];
}
};
``````

• 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;`

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