编程开发中如何实现最小编辑距离

发布时间:2021-11-25 09:25:14 作者:小新
来源:亿速云 阅读:159

这篇文章将为大家详细讲解有关编程开发中如何实现最小编辑距离,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

题目描述:

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

# -*- coding: utf-8 -*-

class Solution:
    """
    从word1->word2,对于word1的每个字符,可以有插入、删除、替换三种操作。
    碰到这种题我们应该先想到的是这是一道可以用动态规划解决的问题,因为我们是要从一个复杂的问题中
    求解一个最优值,而这个复杂问题可以分解成多个子问题。例如,我们已经将word1[:-1]到word2的最小
    编辑距离找到了,那么再计算word1->word2的编辑距离的时候就会变得容易许多。

    既然已经知道要用到动态规划,那么动态规划的解题步骤就是先找出状态转移方程,然后对状态进行初始化

    假设dp[i][j]代表将word1[:i] -> word2[:j]所需的最小编辑距离,那么当我们已知dp[i-1][j-1]
    的时候,要求dp[i][j]的话可以有以下两种情况:
    1. word1[i - 1] == word2[j - 1]:
        这种情况我们不需要对word1[i-1]做任何操作,等价于dp[i-1][j-1]
        即:dp[i][j] = dp[i-1][j-1]
    2. word1[i - 1] != word2[j - 1]:
        这时候我们要想到,我们已经用一个二维的状态矩阵保存了不同情况下的最优值,应该要想办法利用已
        知的最优值来找到当前状态的最优值。

        a) 删除
        由于我们已知dp[i - 1][j],这代表了将word1[: i - 1]->word2[: j]的最小编辑距离,
        如果我们先将word1[: i - 1]->word2[: j],然后将word1[i - 1]删除,那么就可以实现
        word1[:i] -> word2[:j].
        因此,dp[i][j] = dp[i - 1][j] + 1;
        b) 插入
        由于我们已知dp[i][j - 1],这代表了将word1[: i]->word2[: j - 1]的最小编辑距离,
        如果我们先将word1[: i]->word2[: j - 1],然后再在word1[: i]后面增加word2[j - 1]
        那么就可以实现word1[:i] -> word2[:j]。
        因此,dp[i][j] = dp[i][j - 1] + 1
        c) 替换
        由于我们已知dp[i - 1][j - 1],这代表了将word1[: i - 1]->word2[: j - 1]的
        最小编辑距离,如果我们先将word1[: i - 1]->word2[: j - 1],然后再将word1[i]替换成
        word2[j],那么就可以实现word1[:i] -> word2[:j]。
        那么也可以实现word1[:i] -> word2[:j]。
        因此,dp[i][j] = dp[i - 1][j - 1] + 1

        上述的a)b)c)都是可行的,而我们需要的是最小的编辑距离,因此就需要从上述的三种操作中选择
        最小的一种
    """
    def minDistance(self, word1: str, word2: str) -> int:
        rows = len(word1)
        cols = len(word2)
        # 初始化状态矩阵
        dp = [[0] * cols for _ in range(rows)]
        for i in range(cols):
            dp[0][i] = i
        for j in range(rows):
            dp[j][0] = j

        # 根据状态转换方程进行状态更新
        for i in range(1, rows):
            for j in range(1, cols):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1],
                                       dp[i - 1][j - 1])

        # 动态规划的最后一个状态就是我们需要的结果
        return dp[-1][-1]

关于“编程开发中如何实现最小编辑距离”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

推荐阅读:
  1. 编程开发中如何实现文件版本通讯录
  2. 编程开发中如何实现布隆过滤器

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

编程开发

上一篇:如何理解.NET Framework 4.0功能特点

下一篇:python的类方法classmethod怎么使用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》