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


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

Log in to reply
 

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