My DP solution (recursive)


  • 2
    J
    class Solution {
    public:
        int _minDistance(string word1, string word2, vector<vector<int> > &m, int l1, int l2) {
            if (m[l1][l2] != -1)
                return m[l1][l2];
            if (l1 == 0 || l2 == 0) {
                m[l1][l2] = l1 > l2 ? l1 : l2;
                return m[l1][l2];
            }
            int d1 = _minDistance(word1, word2, m, l1 - 1, l2) + 1;
            int d2 = _minDistance(word1, word2, m, l1, l2 - 1) + 1;
            int d3 = _minDistance(word1, word2, m, l1 - 1, l2 - 1) + (word1[l1 - 1] != word2[l2 - 1] ? 1 : 0);
            m[l1][l2] = d1 < d2 ? d1 : d2;
            m[l1][l2] = m[l1][l2] < d3 ? m[l1][l2] : d3;
            return m[l1][l2];
        }
        
        int minDistance(string word1, string word2) {
            int nr = word1.size();
            int nc = word2.size();
            vector<vector<int> > matrix;
            vector<int> *curr;
            int i, j;
            for (i = 0; i <= nr; ++i) {
                curr = new vector<int>(nc + 1);
                for (j = 0; j <= nc; ++j)
                    (*curr)[j] = -1;
                matrix.push_back(*curr);
            }
            return _minDistance(word1, word2, matrix, nr, nc);
        }
    };
    

    see http://en.wikipedia.org/wiki/Levenshtein_distance for algorithm reference.


Log in to reply
 

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