72. 编辑距离

题目

给你两个单词 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')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

解答

思路：记忆化搜索

回溯三问：

• 当前操作：
  • 插入：在 s[i] 后面插入一个数字，可以插入 t[j]，就等于在 t 中删除 t[j]
  • 删除：删除 s[i]
  • 替换：将 s[i] 替换为 t[j]
• 当前问题：s[0..i] 到 t[0..j] 的 最小 操作次数，递归函数为 dfs(i, j)，返回操作次数
• 它的子问题：
  • 插入：dfs(i, j - 1)
  • 删除：dfs(i - 1, j)
  • 替换：dfs(i - 1, j - 1)
  • 如果 s[i] == t[j]，那么也是 dfs(i - 1, j - 1)

递归关系式：

$$\text{dfs}(i,j)=\{\begin{array}{rlrl}& \text{dfs}(i-1,j-1)& & s[i]=t[j]\\ & min(\text{dfs}(i-1,j),\text{dfs}(i,j-1),\text{dfs}(i-1,j-1))+1& & s[i]\ne t[j]\end{array}$$

那么在 s[i] == t[j] 的情况下，我们需要考虑 dfs(i - 1, j) 和 dfs(i, j - 1) 吗？不用考虑了，证明方法和 1143 一样。

代码

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        @cache
        def dfs(i, j):
            if i < 0:
                return j + 1
            
            if j < 0:
                return i + 1
            
            if s[i] == t[j]:
                return dfs(i - 1, j - 1)
            
            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1
        
        return dfs(n - 1, m - 1)

思路：递推

改写成递推关系式：

$$f[i][j]=\text{-}\{\begin{array}{ll}f[i-1][j-1]& s[i]=t[j]\\ min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1& s[i]\ne t[j]\end{array}$$

下标改为正数：

$$f[i+1][j+1]=\{\begin{array}{ll}f[i][j]& s[i]=t[j]\\ min(f[i+1][j],f[i][j+1],f[i][j])+1& s[i]\ne t[j]\end{array}$$

注意 i, j 坐标均 + 1 了。

代码

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0] = list(range(m + 1))
        
        for i, x in enumerate(s):
            f[i + 1][0] = i + 1 # f[i][0] = i，下标 +1 了
            for j, y in enumerate(t):
                if x == y:
                    f[i + 1][j + 1] = f[i][j]
                else:
                    f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1], f[i][j]) + 1
        
        return f[n][m]

思路

代码

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = list(range(m + 1))

        for i, x in enumerate(s):
            pre = f[0]
            f[0] += 1 # f[i][0] = i

            for j, y in enumerate(t):
                tmp = f[j + 1]

                if x == y:
                    f[j + 1] = pre # 斜上方的值
                else:
                    f[j + 1] = min(f[j], f[j + 1], pre) + 1
                
                pre = tmp

        return f[m]