# My Accepted Java Solution

• Hi:

This is a very interesting question and I found a youtube video that helps a lot.
Basically the idea is to build up the solution step by step and keep track of the previous optimal solution in a 2D array. In this 2D array dp, dp[i][j] means the operation needed to transform word1(0, i) to word2(0,j).

There can be three conditions:

1, word1[i] == word2[j] : then no operation needed. dp[i][j] == dp[i-1][j-1]

2, Do one operation on word1[i-1][j]. dp[i][j] = dp[i-1][j] + 1

3, Do one operation on word2[i][j-1]. dp[i][j] = dp[i][j-1] + 1

for 2 and 3, the reason it works is that we know the optimal ways to transfrom word1(0,i) to word2(0,j-1) and word1(0,i-1) to word(0,j) ( Delete ("abc" to "ab") or Insert ("ab" to "abc") ). Now all we need to one more operation.

The code will be:

``````public int minDistance(String word1, String word2) {
if (word1.equals(word2)) {
return 0;
}
if (word1.length() == 0 || word2.length() == 0) {
return Math.abs(word1.length() - word2.length());
}
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int i = 0; i <= word2.length(); i++) {
dp[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
``````

Remeber that we start from dp[0][0], which is an empty string to an empty string.

• Nice solution

• great explanation

• Nice! I think it is similar with LCS.

• Great explanation, however, I think when word1[i] == word2[j] :

``````dp[i][j] == min(dp[i-1][j-1], dp[i-1][j] + 1, dp[i][j-1] + 1)
``````

Because "dp[i-1][j] + 1" or "dp[i][j-1] + 1" may less than "dp[i-1][j-1]".

• greate! your solution is easy to understand.

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