Good pdf on edit distance problem. May be helpful.


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; };

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).

I found this youtube video very helpful. https://www.youtube.com/watch?v=We3YDTzNXEk&index=27&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr