72. Edit Distance.md

72. Edit Distance

思路

求编辑距离：给定两个字符串word1和word2，求word1经过几次操作能变成word2。

根据经验，这种求最值的两个字符串类的问题基本都可以用动归（因为整个问题可以分解成多个子问题求解而且子问题之间有重复），这里也不例外。我们定义

dp[i][j] 表示字符串word1[0,1,...,i-1]和word1[0,1,...,j-1]的编辑距离

需要仔细考虑一下初始情况，即当两个串中有一个空串时编辑距离就为另一个串的长度，所以我们可以按照下面初始化：

dp[0][0] = 0; // 两个空串
for(int i = 1; i <= n1; i++) dp[i][0] = i; // word2是空串
for(int i = 1; i <= n2; i++) dp[0][i] = i; // word1是空串

状态转移时有两种情况：

1. word1[i-1] == word2[j-1]，那么此时很简单dp[i][j] = dp[i-1][j-1], dp[i][j]；
2. 否则，我们需要分别对word1末尾进行插入、删除和替换，取三者最小结果即可，即dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))。

可见状态数组里的元素dp[i][[j]只与左上三个方向的值（dp[i-1][j-1], dp[i][j-1], dp[i-1][j]）有关，所以可用滚动数组优化空间至线性。

时间复杂度O(mn)，空间复杂度O(mn)（可优化至O(n)）

C++

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        
        vector<vector<int>>dp(n1 + 1, vector<int>(n2 + 1, 0));
        for(int i = 1; i <= n1; i++) dp[i][0] = i;
        for(int i = 1; i <= n2; i++) dp[0][i] = i;
        
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1], dp[i][j];
                else dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]));
            }
        }
        return dp[n1][n2];
    }
};