Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a characterb) Delete a characterc) Replace a character
Show Tags
这题刚开始感觉就是DP，后来看到了Discuss里面给出的pdf链接才知道怎么做。
我们令dp[i][j]表示word1的前i个字母和word2的前j个字母的差距数，那么：
Just felt that maybe dynamic programming should be used to solve this problem, but not until i read the pdf from the Discuss did i know how to use dp.
Define the dp[i][j] the edit distance between the first i letters from word1 and the first j letters from word2, we get:
我的AC代码：
My AC code:
class Solution {public:int minDistance(string word1, string word2) {int s1 = word1.size(), s2 = word2.size();int ** dp; // new an arraydp = new int*[s1 + 1];for (int i = 0; i <= s1; i++) dp[i] = new int[s2 + 1];for (int i = 0; i <= s1; i++) dp[i][0] = i; // initialisefor (int i = 0; i <= s2; i++) dp[0][i] = i;for (int i = 1; i <= s1; i++) {for (int j = 1; j <= s2; j++) {dp[i][j] = min(min(dp[i – 1][j] + 1, dp[i][j – 1] + 1), dp[i – 1][j – 1] + (word1[i – 1] != word2[j – 1]));}}int ans = dp[s1][s2]; // record the answerfor (int i = 0; i < s1; i++) delete []dp[i]; // delete the arraydelete[]dp;return ans;}};如果我们需要知道是如何把word2改变成word1的应该如何做呢？
建立另外一个导向数组，，回溯即可。
这是来用来研究的代码：
But what if we wanna know how to convert word2 to word1?
We can use an array to trace to get the answer.
Let’s see this code(just add sth. from the above):
#include <iostream>#include <string>#include <vector>#include <iomanip>using namespace std;class Solution {public:int minDistance(string word1, string word2) {int s1 = word1.size(), s2 = word2.size();int ** dp; // new a dp arraydp = new int*[s1 + 1];for (int i = 0; i <= s1; i++) dp[i] = new int[s2 + 1];for (int i = 0; i <= s1; i++) dp[i][0] = i;for (int i = 0; i <= s2; i++) dp[0][i] = i;string ** dir; // new a direction arraydir = new string*[s1 + 1];for (int i = 0; i <= s1; i++) dir[i] = new string[s2 + 1];for (int i = 0; i <= s1; i++) dir[i][0] = "Insert"; // insert sth. to word1for (int i = 0; i <= s2; i++) dir[0][i] = "Delete"; // delete sth. from word1dir[0][0] = " Start"; // begin the conversionfor (int i = 1; i <= s1; i++) {for (int j = 1; j <= s2; j++) {int ins, del, rep;ins = dp[i – 1][j] + 1;del = dp[i][j – 1] + 1;rep = dp[i – 1][j – 1] + (word1[i – 1] != word2[j – 1]);if (ins <= del && ins <= rep) {dp[i][j] = ins;dir[i][j] = "Insert";}else if (del <= ins && del <= rep) {dp[i][j] = del;dir[i][j] = "Delete";}else if (rep <= ins && rep <= del) {dp[i][j] = rep;if (word1[i – 1] != word2[j – 1]) {dir[i][j] = "Change"; // change some letters in word2 to word1}else {dir[i][j] = " Keep"; // keep some letters in word1}}}}cout << "Steps:" << endl; // show the dp arraycout << "#";for (int i = 0; i < s2; i++) cout << "" << word2[i];cout << endl;for (int i = 0; i <= s1; i++) {cout << (i == 0 ? '#' : word1[i – 1]);for (int j = 0; j <= s2; j++) {cout << setw(7) << dp[i][j];}cout << endl << endl;}cout << "How: " << endl; // show the direction arraycout << "#";for (int i = 0; i < s2; i++) cout << "" << word2[i];cout << endl;for (int i = 0; i <= s1; i++) {cout << (i == 0 ? '#' : word1[i – 1]);for (int j = 0; j <= s2; j++) {cout << " " << dir[i][j];}cout << endl << endl;}cout << "From Word2 to Word1:" << endl; // traceint si = s1, sj = s2;vector<string> fromWord2ToWord1;for (int i = 0; i < dp[s1][s2];) {fromWord2ToWord1.push_back(dir[si][sj]);if (dir[si][sj] != " Keep") i++;if (dir[si][sj] == "Insert") si–;else if (dir[si][sj] == "Delete") sj–;else si–, sj–;}for (int i = fromWord2ToWord1.size() – 1; i >= 0; i–) {cout << fromWord2ToWord1[i] << (i ? " –> " : ".");}cout << endl << endl;int ans = dp[s1][s2];for (int i = 0; i < s1; i++) delete []dp[i];delete[]dp;return ans;}};int main() {Solution s;cout << "Ans:" << s.minDistance("abcdxabcdasde", "qwkvokasd");return 0;}让我们看看发生了什么：
这里的例子是word1="abcdxabcdasde"，word2="qwkyokasd"，注意我们是将word2转为word1，反过来情况类似;
dp数组的变化：
Notice that theword1 is "abcdxabcdasde" and the word2 is "qwkyokasd".
This is what happened in the dp array:
如果你不出去走走，你就会以为这就是世界。
