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

题目主要信息:

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM66.最长公共子串

BM71.最长上升子序列(一)

BM73 最长回文子串

BM76 正则表达式匹配

BM77 最长的括号子串

方法：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用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$。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int editDistance (String str1, String str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        //dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        int[][] dp = new int[n1 + 1][n2 + 1]; 
        //初始化边界
        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.charAt(i - 1) == str2.charAt(j - 1)) 
                    //直接等于二者前一个的距离
                    dp[i][j] = dp[i - 1][j - 1]; 
                else
                    //选取最小的距离加上此处编辑距离1
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; 
            }
        return dp[n1][n2]; 
    }
}

C++实现代码：

class Solution {
public:
    int editDistance(string str1, string str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        //dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0)); 
        //初始化边界
        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
                    //选取最小的距离加上此处编辑距离1
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; 
            }
        return dp[n1][n2]; 
    }
};

Python代码实现：

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

复杂度分析：

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