LeetCode 72. 编辑距离 python-白红宇

LeetCode 72. 编辑距离 python

阅读量：632 次

发布时间：2019-03-14

本文共 579 字，大约阅读时间需要 1 分钟。

编辑距离的问题可以用动态规划的方法来高效解决。以下是详细的解题思路：

设两个单词分别为 word1 和 word2，分别具有长度 n 和 m。我们需要求出将 word1 转换为 word2 所需的最小操作数。

我们可以使用一个 (n+1) x (m+1) 的二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符与 word2 的前 j 个字符处理后的最小编辑距离。

边界条件

当 word1 或 word2 为空时，我们只能进行插入或删除操作。因此，dp[i][0] = i，dp[0][j] = j，其中 i 和 j 分别表示各自字符串的长度。

递推公式

如果 word1[i-1] == word2[j-1]，则不需要任何替换操作，于是 dp[i][j] = dp[i-1][j-1]。

否则，dp[i][j] = min替换、删除、插入) + 1：

替换：dp[i-1][j-1] + 1

删除：dp[i-1][j] + 1

插入：dp[i][j-1] + 1

优化空间复杂度

可以只使用一行来保存当前的状态，节省空间。我们只需要每次计算当前行的j值时，用上一行的j-1到j的信息。

时间复杂度

该算法的时间复杂度为 O(nm)，空间复杂度为 O(m)（使用一维数组）。

最终答案是 dp[n][m]，即两个单词的最小编辑距离。

转载地址：http://vrxoz.baihongyu.com/

你可能感兴趣的文章

pip install goose-extractor // SyntaxError: Missing parentheses in call to 'print'

查看>>

pip install mysqlclient报错

查看>>

pip install 出现报asciii码错误的解决

查看>>

pip throws TypeError: parse() got an unexpected keyword argument ‘transport_encoding‘ 在尝试安装新软件包时

查看>>

pip 下载慢

查看>>

pip 升级报错AttributeError: ‘NoneType’ object has no attribute ‘bytes’

查看>>

pip 安装opencv-python卡死

pip 或 pip3 为 Python 3 安装包?

查看>>

pip 文件损坏导致 pip无法使用报错 ImportError: cannot import name 'main' from 'pip._int

查看>>

pip 无法从 requirements.txt 安装软件包

查看>>

pip/pip3更换国内源

查看>>

pip3 install PyQt5 --user 失败

查看>>

pip3命令全解析：Python3包管理工具的详细使用指南

查看>>

pip3安装命令重复创建文件‘/tmp/pip-install-xxxxx/package‘失败

查看>>

PIPE 接口信号列表

查看>>

pipeline配置与管理Job企业级实战

查看>>

pipeline项目配置实战

查看>>