# Java solution using DP

• public int minDistance(String word1, String word2) {
if(word1 == null || word2 == null) {
return Math.max(word1.length(), word2.length());
}

``````        word1 = "#" + word1;
word2 = "#" + word2;
int[][] Distance = new int[word1.length()][word2.length()];
// Initialization
for(int i = 0; i < word1.length(); i++) {
Distance[i][0] = i;
}

for(int j = 0; j < word2.length(); j++) {
Distance[0][j] = j;
}

// Recurrence Relation:
for(int i = 1; i < word1.length(); i++) {
for(int j = 1; j < word2.length(); j++) {

Distance[i][j] = Math.min(Distance[i-1][j], Distance[i][j-1]) + 1;

int temp = 0;
if (word1.charAt(i) == word2.charAt(j)) {
temp =  Distance[i-1][j-1];
} else {
temp = Distance[i-1][j-1] + 1;
}

Distance[i][j] = Math.min(Distance[i][j], temp);
}
}

return Distance[word1.length()-1][word2.length()-1];
}``````

• I just change the item:
temp = Distance[i-1][j-1] + 2 (I thought the cost should be 2) to temp = Distance[i-1][j-1] + 1
Accepted!

• I think the distance from [i-1][j-1] to [i][j] is 1(insert or replace, cause we don't need to edit word2[j]). I used the solution above to judge and accepted as well.

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