Problem:
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Idea:
Dynamic Programming
Solution:
Recursive
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Runtime: 13 ms class Solution { public: int minDistance(string word1, string word2) { int l1 = word1.length(); int l2 = word2.length(); d_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, -1)); return minDistance(word1, word2, l1, l2); } private: vector<vector<int>> d_; // minDistance from word1[0:l1-1] to word2[0:l2-1] int minDistance(const string& word1, const string& word2, int l1, int l2) { if (l1 == 0) return l2; if (l2 == 0) return l1; if (d_[l1][l2] >= 0) return d_[l1][l2]; int ans; if (word1[l1 - 1] == word2[l2 - 1]) ans = minDistance(word1, word2, l1 - 1, l2 - 1); else ans = min(minDistance(word1, word2, l1 - 1, l2 - 1), min(minDistance(word1, word2, l1 - 1, l2), minDistance(word1, word2, l1, l2 - 1))) + 1; return d_[l1][l2] = ans; } }; |
Iterative
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua // Runtime: 9 ms class Solution { public: int minDistance(string word1, string word2) { int l1 = word1.length(); int l2 = word2.length(); // d[i][j] := minDistance(word1[0:i - 1], word2[0:j - 1]); vector<vector<int>> d(l1 + 1, vector<int>(l2 + 1, 0)); for (int i = 0; i <= l1; ++i) d[i][0] = i; for (int j = 0; j <= l2; ++j) d[0][j] = j; for (int i = 1; i <= l1; ++i) for (int j = 1; j <= l2; ++j) { int c = (word1[i - 1] == word2[j - 1]) ? 0 : 1; d[i][j] = min(d[i - 1][j - 1] + c, min(d[i][j - 1], d[i - 1][j]) + 1); } return d[l1][l2]; } }; |