跳到主要内容

编辑题库

编辑距离​

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例1:

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例2:

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

方案 动态规划​

思路: 题目给定了两个单词，设为A和B,这样我们就能够六种操作方法:

  • 对单词A删除一个字符和对单词B插入一个字符是等价的。
  • 同理,对单词B删除一个字符和对单词A插入一个字符也是等价的
  • 对单词A替换一个字符和对单词B替换一个字符是等价的。

这样一来，本质不同的操作实际上只有三种:

  • 在单词A中插入一个字符
  • 在单词B中插入一个字符
  • 修改单词A中的一个字符

因此，我们就可以使用动态规划来解决这个问题了。

  1. 状态定义: dp[i][j]表示A的前i个字母和B的前j个字母之间的编辑距离。
  2. 状态转移方程:
    • 如果A和B的最后一个字母相同，则方程为:dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1])
    • 如果A和B的最后一个字母不同,则方程为:dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
  3. 状态初始化:
    • dp 初始化为0
    • 如果A字符串为0时: dp[0][j]=j
    • 如果B字符串为0时: dp[i][0]=i
  4. 问题答案: dp[row][col]为最终答案

:::details 点击查看代码

function minDistance(word1, word2) {
    const row=word1.length;
    const col=word2.length;
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0))
    for(let i=0;i<=row;i++){
        dp[i][0]=i;
    }
    for(let i=0;i<=col;i++){
        dp[0][i]=i;
    }
    for(let i=1;i<=row;i++){
        for(let j=1;j<=col;j++){
            let start=dp[i-1][j]+1;
            let end=dp[i][j-1]+1;
            let middle=dp[i-1][j-1];
            if(word1[i-1]!=word2[j-1]){
                middle+=1;
            }
            dp[i][j]=Math.min(...[start,end,middle]);
        }
    }
    return dp[row][col];
};

:::

性能分析:

  • 时间复杂度 ：O(mn)
  • 空间复杂度 ：O(mn)

两个字符串的删除操作​

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例1:

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

方案 动态规划​

思路:直接使用动态规划来求解删除次数。

  1. 状态定义: dp[i][j] 表示 s1 串前 i 个字符和 s2 串前 j 个字符匹配的最少删除次数
  2. 状态转移方程:
    • 如果 s1[i-1] 与 s2[j-1] 匹配，dp[i][j]=dp[i-1][j-1]
    • 如果 s1[i-1] 与 s2[j-1] 不匹配，dp[i][j]=min(dp[i][j-1],dp[i-1][j-1])+1
  3. 状态初始化: i 和 j 初始为0
  4. 问题答案: dp[m][n] 就是所求解的最少删除次数。m 和 n 分别是字符串 s1 和字符串 s2 的长度。

:::details 点击查看代码

function minDistance(word1, word2) {
    const len1=word1.length;
    const len2=word2.length;
    let dp=new Array(len1+1).fill(0).map(value=>new Array(len2+1).fill(0));
    for(let i=0;i<=len1;i++){
        for(let j=0;j<=len2;j++){
            if(i==0||j==0){
                dp[i][j]=i+j;
            }else if(word1[i-1]==word2[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
    }
    return dp[len1][len2];
};

:::

性能分析:

  • 时间复杂度：O(m*n)。我们需要求出大小为 m * n 的 dp 数组，m 和 n 分别是两个字符串的长度。
  • 空间复杂度：O(m*n)。使用了大小为 m * n 的 dp 数组。

两个字符串的最小 ASCII 删除和​

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

方案 动态规划​

思路:

  1. 状态定义:
    • s1[i:]表示字符串s1从第i位到末尾的子串
    • s2[j:]表示字符串s2从第j位到末尾的子串
    • dp[i][j]表示字符串s1[i:]和s2[j:]达到相等所需删除的字符的ASCII值得最小和，最终得答案为dp[0][0]
  2. 状态转移方程:
    • 当s1[i:]或者s2[j:]中得某一个字符串为空时，dp[i][j]的值即为另一个非空字符串的所有字符的ASCII值之和
      • 如果s2[j:]为空：可得方程为:dp[i][j]=dp[i+1][j]+s1.charCodeAt(i)
      • 如果s1[i:]为空：可得方程为:dp[i][j]=dp[i][j+1]+s2.charCodeAt(j)
    • 当s1[i:]且s2[j:]都不为空时:
      • 如果有s1[i]==s2[j],方程为:dp[i][j]=dp[i+1][j+1]
      • 如果有s1[i]!=s2[j],方程为:dp[i][j]=min(dp[i+1][j]+s1.charCodeAt(i),dp[i][j+1]+s2.charCodeAt(j))
  3. 初始化状态:
  4. 问题答案: dp[0][0]

:::details 点击查看代码

function minimumDeleteSum(s1, s2) {
    const row=s1.length;
    const col=s2.length;
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0))
    for(let i=row-1;i>=0;i--){
        dp[i][col]=dp[i+1][col]+s1.charCodeAt(i);
    }
    for(let i=col-1;i>=0;i--){
        dp[row][i]=dp[row][i+1]+s2.charCodeAt(i);
    }
    for(let i=row-1;i>=0;i--){
        for(let j=col-1;j>=0;j--){
            if(s1[i]==s2[j]){
                dp[i][j]=dp[i+1][j+1];
            }else{
                dp[i][j]=Math.min(dp[i+1][j]+s1.charCodeAt(i),dp[i][j+1]+s2.charCodeAt(j));
            }
        }
    }
    return dp[0][0];
};

:::

性能分析:

  • 时间复杂度：O(|S_1|* |S_2|)。
  • 空间复杂度：O(|S_1|* |S_2|)