Good pdf on edit distance problem. May be helpful.


  • 46

  • 0
    Y

    The pdf is not completely right. It has
    d[i][j] = d[i-1][j-1] + 2 when S1[i] != S2[j].
    It should be
    d[i][j] = d[i-1][j-1] + 1


  • 2
    N

    That's depend on the operation weight. In that paper, it assume replace weighted 2 (consider as a delete followed by insert), insert/delete weighted 1.


  • 1
    H

    Just curious, how many hours one would spend to come up with a solution if he/she never heard about "Edit Distance" term?


  • 0
    O

    I don't think that anyone who is not genius can think up with this ideas in any given time... It's crazily brilliant. How do you come up with the idea of each operation to elements in a matrix!? It's so NOT intuitive!!


  • 0
    R

    Hi,
    I tried to implement the idea, can someone please tell me the complexity of my code? this is not O(n)optimized version, but I wonder what is the space and time complexity of my solution?

    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
    K

    recursive solution easy to think but reduction from recursive to matrix based solution takes a lot of thought process anyone can do who knows DP but how much time he takes depends on his thought process.


  • 0
    E

    Thanks, I found this pdf useful. Actually, it reminds me what I have learned in my Basic Bioinformatic class in college. It's a relatively important problem in computational biology, by solving which, we can align two sequences of Nucleotides, track the way to achieve it and compute its cost(score).


  • 1

  • 0
    J

    Good Video! This guy also has a video on KMP algorithm for string search, which is also very good.


Log in to reply
 

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