leetcode

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

---

算法

O(n^2) DP https://segmentfault.com/a/1190000003741294

---

class Solution { public: int minDistance(string word1, string word2) { if (word1.length() < word2.length()) swap(word1, word2); vector<int> dp(word2.length() + 1); // word2 will cost less space // init for (int i = 0; i < dp.size(); ++i) dp[i] = i; int upleft = 0; // Record the dp[i-1][j-1]. It must be used. for (int i = 1; i <= word1.size(); ++i) { upleft = dp[0]; dp[0] = i; for (int j = 1; j <= word2.size(); ++j) { int rec = dp[j]; if (word1[i - 1] == word2[j - 1]) dp[j] = upleft; else dp[j] = min(upleft, min(dp[j], dp[j - 1])) + 1; upleft = rec; } } return dp[word2.length()]; } };