题解 | #编辑距离(一)#

题目主要信息:

• 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符
• 求增删改的最少次数，让第一个字符串变成第二个字符串
• 字符串中只出现大小写字母

具体思路:

把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，那很明显dp[str1.length][str2.length]就是我们要求的编辑距离。（下标从1开始）

• step 1：初始条件： 假设第二个字符串为空，那很明显第一个字符串子串每增加一个字符，编辑距离就加1，这步操作是删除；同理，假设第一个字符串为空，那第二个字符串每增加一个字符，编剧距离就加1，这步操作是添加。
• step 2：状态转移： 状态转移肯定是将dp矩阵填满，那就遍历第一个字符串的每个长度，对应第二个字符串的每个长度。如果遍历到str1[i]和 str2[j]的位置，这两个字符相同，这多出来的字符就不用操作，操作次数与两个子串的前一个相同，因此有$dp[i][j]=dp[i-1][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]$；如果这两个字符不相同，那么这两个字符需要编辑，但是此时的最短的距离不一定是修改这最后一位，也有可能是删除某个字符或者增加某个字符，因此我们选取这三种情况的最小值增加一个编辑距离，即$dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1dp[i][j]\; =\; min(dp[i\; -\; 1][j\; -\; 1],\; min(dp[i\; -\; 1][j],\; dp[i][j\; -\; 1]))\; +\; 1$。

具体状态转移过程可以参考如下图：

代码实现:

class Solution {
public:
    int editDistance(string str1, string str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0)); //dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        for(int i = 1; i <= n1; i++) //初始化边界
            dp[i][0] = dp[i - 1][0] + 1;
        for(int i = 1; i <= n2; i++)
            dp[0][i] = dp[0][i - 1] + 1;
        for(int i = 1; i <= n1; i++) //遍历第一个字符串的每个位置
            for(int j = 1; j <= n2; j++){ //对应第二个字符串每个位置
                if(str1[i - 1] == str2[j - 1]) //若是字符相同，此处不用编辑
                    dp[i][j] = dp[i - 1][j - 1]; //直接等于二者前一个的距离
                else
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; //选取最小的距离加上此处编辑距离1
            }
        return dp[n1][n2]; 
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$、$nn$分别为两个字符串的长度，初始化dp数组单独遍历两个字符串，后续动态规划过程两层遍历
• 空间复杂度：$o(mn)o(mn)$，辅助数组dp的空间