# My DP solution (recursive)

• ``````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.

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