LeetCode-Edit Distance

编辑距离，很常见的题目，貌似去年google笔试就考了这道题，

典型的DP，dp[i][j]表示word2[i]到word1[j]的最小编辑距离；

当word2[i]与word1[j]不相同时有三种方式：

1.改变字符，dp[i][j] = dp[i - 1][j- 1] + 1;

2.插入字符，dp[i][j] = dp[i ][j - 1] + 1;

3.删除字符，dp[i][j] = dp[i - 1][j] + 1;

故dp[i][j] = min(1,2,3);

当word2[i]与word1[j]相同时：

dp[i][j] = dp[i - 1][j - 1];

 1 class Solution {
 2 public:
 3     int minDistance(string word1, string word2) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int m = word1.size(), n = word2.size();
 7         vector<vector<int> > dp(n + 1, vector<int>(m + 1));
 8         for (int i = 0; i <= n; ++i)
 9             dp[i][0] = i;
10         for (int j = 0; j <= m; ++j)
11             dp[0][j] = j;
12         for (int i = 1; i <= n; ++i)
13             for (int j = 1; j <= m; ++j) {
14                 if (word2[i - 1] == word1[j - 1])
15                     dp[i][j] = dp[i - 1][j - 1];
16                 else 
17                     dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
18             }
19         return dp[n][m];
20     }
21 };

不过看到还有更好的方法，可以把空间复杂度降低到O(n)，

n = word2.length();

dp[n + 1], dp[i]记录到word2[i]的最小编辑距离，

动态更新的过程要巧妙一点，从word1的开始逐步更新，

计算word1的(0, word1[i])到word2[j]的最小编辑距离，

更新dp[j];

递推过程：

当更新word1的第i个字符时，dp[j]中存的是上一步的值，即word[i - 1]与word2[j]的距离；

相当于前一种方法中的dp[i - 1][j]，

按0<= j <=n 遍历word2，

dp[j]相当于dp[i - 1][j];

dp[j - 1]相当于dp[i - 1][j - 1];

在更新dp[j]为当前这一步（即遍历到word1[i]）的值时，

当字符相同时：

当前的距离cur = dp[i - 1][j - 1] = dp[j - 1]，

由于要用到上一步的dp[j - 1]，所以使用之后才能更新；

当字符不同时：

1.改变字符，cur = dp[i - 1][j- 1] + 1;

2.插入字符，cur = dp[i ][j - 1] + 1;

3.删除字符，cur = dp[i - 1][j] + 1;

1,3都要用到上一步的dp[j - 1], dp[j];

2为当前这一步已经更新了的dp[j - 1]，

所以这里无法用dp[j - 1]表示两个值，故可以用一个变量pre记录当前上一次的值pre = dp[i][j - 1];

当执行到j时，

更新dp[j -1] = pre，然后令 pre = cur = dp[j]；

 1 class Solution {
 2 public:
 3     int minDistance(string word1, string word2) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (word1.empty()) {
 7             return word2.size();
 8         }
 9         if (word2.empty()) {
10             return word1.size();
11         }
12         int m = word1.size(), n = word2.size();
13         int i = 0;
14         vector<int> dp(n + 1, 0);
15         for (int i = 0; i <= n; ++i)
16             dp[i] = i;
17         for (int i = 1; i <= m; ++i) {
18             int pre = i;
19             int cur = i;
20             for (int j = 1; j <= n; ++j) {
21                 if (word1[i - 1] == word2[j - 1])
22                     cur = dp[j - 1];
23                 else
24                     cur = min(min(dp[j - 1], dp[j]), pre) + 1;            
25                 dp[j - 1] = pre;
26                 pre = cur;
27             }
28             dp[n] = cur;
29         }
30         return dp[n];
31     }
32 };