# Java 13ms O(n^2) DP Solution With Explanation, 28 lines, O(n) Space

• Corner Case: If either string is empty, the minimum edit distance is another string's length.

• Use d(s1,s2) stands for the shortest edit distance from s1 to s2, we can get the following transition:

``````d(s1,s2) ={
if(s1[i] == s2[j]){
min(
d(s1-1,s2)+1,   //Delete
d(s1,s2-1)+1,   //Insert
d(s1-1,s2-1),  //Same
)
}
else{
min(
d(s1-1,s2)+1,   //Delete
d(s1,s2-1)+1,   //Insert
d(s1-1,s2-1)+1, //Replace
)
}
}
``````
``````public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if(len2 == 0) return len1;
if(len1 == 0) return len2;
int[] w2 = new int[len2+1];
int[] temp = new int[len2+1];
for(int j = 0; j <= len2; j++) w2[j] = j;
for(int i = 1; i <= len1; i++){
int prev = i;
temp[0] = prev;
for(int j = 1; j <= len2; j++){
int min = Math.min(w2[j-1],w2[j]);
min = Math.min(min, prev);
if(word1.charAt(i-1) == word2.charAt(j-1) && min == w2[j-1]){
temp[j] = min;
}
else{
temp[j] = min+1;
}
prev = temp[j];
}
w2 = temp.clone();
}
return w2[len2];
}
}
``````

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