My O(mn) time and O(n) space solution using DP with explanation


  • 73
    E

    Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):

    if c == d, then : f[i][j] = f[i-1][j-1]

    Otherwise we can use three operations to convert word1 to word2:

    (a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;

    (b) if we added d after c: f[i][j] = f[i][j-1] + 1;

    (c) if we deleted c: f[i][j] = f[i-1][j] + 1;

    Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).

     int minDistance(string word1, string word2) {
        
            int l1 = word1.size();
            int l2 = word2.size();
        
            vector<int> f(l2+1, 0);
            for (int j = 1; j <= l2; ++j)
                f[j] = j;
        
            for (int i = 1; i <= l1; ++i)
            {
                int prev = i;
                for (int j = 1; j <= l2; ++j)
                {
                    int cur;
                    if (word1[i-1] == word2[j-1]) {
                        cur = f[j-1];
                    } else {
                        cur = min(min(f[j-1], prev), f[j]) + 1;
                    }
        
                    f[j-1] = prev;
                    prev = cur;
                }
                f[l2] = prev;
            }
            return f[l2];
        
        }  
    

    Actually at first glance I thought this question was similar to Word Ladder and I tried to solve it using BFS(pretty stupid huh?). But in fact, the main difference is that there's a strict restriction on the intermediate words in Word Ladder problem, while there's no restriction in this problem. If we added some restriction on intermediate words for this question, I don't think this DP solution would still work.


  • 0
    I

    I like your solution. It's nice and concise!


  • 14
    P

    Thank you!!
    According to your idea, I rewrote the code in Java:

    public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        //distance[i][j] is the distance converse word1(1~ith) to word2(1~jth)
        int[][] distance = new int[len1 + 1][len2 + 1]; 
        for (int j = 0; j <= len2; j++)
            {distance[0][j] = j;} //delete all characters in word2
        for (int i = 0; i <= len1; i++)
            {distance[i][0] = i;}
    
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) { //ith & jth
                    distance[i][j] = distance[i - 1][j - 1];
                } else {
                    distance[i][j] = Math.min(Math.min(distance[i][j - 1], distance[i - 1][j]), distance[i - 1][j - 1]) + 1;
                }
            }
        }
        return distance[len1][len2];        
    }
    

    }


  • 0
    A

    good solution


  • 6
    S

    According to your 1D array space, I modified my original one into this O(n) space version. Also pasting original version for reference.

    public class Solution {
        public int minDistance(String word1, String word2) {
            int opt[] = new int[word2.length()+1];
            // base case
            for(int j = 0;j <= word2.length();j++) opt[j] = j;
            // iteration
            for(int i = 1;i <= word1.length();i++){
                int pre = i, corner = i-1;
                for(int j = 1;j <= word2.length();j++){
                    int temp = corner;
                    corner = opt[j];
                    temp += (word1.charAt(i-1)==word2.charAt(j-1)?0:1); 
                    opt[j] = Math.min(temp,Math.min(opt[j],pre)+1);
                    pre = opt[j];
                }
                opt[word2.length()] = pre;
            }
            return opt[word2.length()];
        }
    }
    

    Original Version

    public class Solution {
        public int minDistance(String word1, String word2) {
            int opt[][] = new int[word1.length()+1][word2.length()+1];
            // base case
            for(int i = 0;i <= word1.length();i++) opt[i][0] = i;
            for(int j = 0;j <= word2.length();j++) opt[0][j] = j;
            // iteration
            for(int i = 1;i <= word1.length();i++)
                for(int j = 1;j <= word2.length();j++)
                    opt[i][j] = Math.min(Math.min(opt[i-1][j]+1,opt[i][j-1]+1),opt[i-1][j-1] + (word1.charAt(i-1)==word2.charAt(j-1)?0:1));
            return opt[word1.length()][word2.length()];
        }
    }

  • 0
    C

    Hi, siyang, thank you for your posting. But I have a confusion in your 1-D array version.
    Isn't "opt[word2.length()] = pre;" redundant since you've alreay did that in the for loop above with "opt[j] = Math.min(temp,Math.min(opt[j],pre)+1)" ?

    Okay, never mind. I just figured out that the reason to keep that line is to handle cases where word2.length() == 0.


  • 0
    S

    Beautiful code ! Thanks for sharing!


  • 0
    R

    Hi,
    Mine is not optimized, but a simple DP solution, can you please tell me the complexity of my code?

        class Solution {
        public:
            int minDistance(string word1, string word2) {
                cache=vector<vector<int>>(word1.size()+1, vector<int>(word2.size()+1,-1));
                return minDistance(word1, 0,  word2, 0);
            }
        private:
            int minDistance(const string& word1, int a, const string& word2, int b) {
                if(a==word1.size() && b==word2.size()) return 0;
                if(a==word1.size()) return word2.size()-b;
                if(b==word2.size()) return word1.size()-a;
                if(cache[a][b]!=-1) return cache[a][b];
                
                if(word1[a]==word2[b]){
                    return cache[a][b]=minDistance(word1, a+1, word2, b+1);
                }else{
                    return cache[a][b]=min(min(minDistance(word1,a+1,word2,b+1),
                                                  minDistance(word1,a,word2,b+1)),
                                                  minDistance(word1,a+1,word2,b))+1; 
                }
            }
            vector<vector<int>> cache;
        };

  • 0
    Y

    So beautiful.


  • 0
    H

    No better explanation than this one. Thumbs up!


  • 0
    G

    it should be the same as iterative solution O(n * m), the dfs time depends on the combination of your two parameters, a, and b;


  • 0
    This post is deleted!

  • 0

    Good job, recalls me the famous LCS problem.


Log in to reply
 

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