动态规划算法解决最小编辑距离问题

li_peixiansang

1068人浏览 · 2024-03-16 14:49:30

li_peixiansang · 2024-03-16 14:49:30 发布

引言

在计算机科学中，最小编辑距离（Levenshtein 距离）是一种常用的度量方法，用于衡量两个字符串之间的相似程度。它表示将一个字符串转换为另一个字符串所需的最少编辑操作次数，编辑操作包括插入一个字符、删除一个字符和替换一个字符。

问题描述

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

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

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

示例 1：

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

题目链接：. - 力扣（LeetCode）

解题思路

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

但我们可以发现，如果我们有单词 A 和单词 B：

对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为 dog 时，我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，得到相同的 doge；

同理，对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的；

对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。

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

在单词 A 中插入一个字符；

在单词 B 中插入一个字符；

修改单词 A 的一个字符。

这样以来，我们就可以把原问题转化为规模较小的子问题

使用动态规划来解决这个问题是非常合适的。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示将 word1 的第 i 个字符转换为 word2 的第 j 个字符所需的最小编辑次数。

根据最小编辑距离的定义，我们可以进行三种操作：

如果 word1[i-1] 等于 word2[j-1]，则不需要进行任何编辑操作，dp[i][j] = dp[i-1][j-1]。
如果 word1[i-1] 不等于 word2[j-1]，则可以考虑进行替换操作，此时 dp[i][j] = dp[i-1][j-1] + 1。
另外，还有插入和删除操作，分别对应 dp[i][j] = dp[i][j-1] + 1 和 dp[i][j] = dp[i-1][j] + 1。

最终，我们可以通过填充 dp 数组得到 dp[-1][-1] 的值，即为最小编辑距离。

Python 实现

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)+1
        n=len(word2)+1
        dp = [[0 for i in range(n)]for i in range(m)]
        # 初始化dp边界
        for i in range(n):
            dp[0][i]=i
        for i in range(m):
            dp[i][0]=i

        for i in range(1, m):
            for j in range(1, n):
                issame=1
                if word1[i-1]==word2[j-1]:
                    issame=0

                dp[i][j]=min(dp[i-1][j-1]+issame, dp[i][j-1]+1, dp[i-1][j]+1)
        return dp[-1][-1]