【力扣72. 编辑距离】dp(Python3)
2021/7/13 17:07:34
本文主要是介绍【力扣72. 编辑距离】dp(Python3),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
https://leetcode-cn.com/problems/edit-distance/
思路题解
https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
状态拆解为3个状态,进行分析:
对“dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。”的补充理解:
以 word1 为 “horse”,word2 为 “ros”,且 dp[5][3] 为例,即要将 word1的前 5 个字符转换为 word2的前 3 个字符,也就是将 horse 转换为 ros,因此有:
- (1) dp[i-1][j-1],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro,然后将第五个字符 word1[4](因为下标基数以 0 开始) 由 e 替换为 s(即替换为 word2 的第三个字符,word2[2])
- (2) dp[i][j-1],即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro,然后在末尾补充一个 s,即插入操作
- (3) dp[i-1][j],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros,然后删除 word1 的第 5 个字符
dp初始状态:
状态转移方程:
class Solution: def minDistance(self, word1: str, word2: str) -> int: n,m = len(word1),len(word2) if n * m == 0:# 有一个字符串为空串 return n + m D = [ [0] * (m + 1) for _ in range(n + 1)] # 边界状态初始化 for i in range(n + 1): D[i][0] = i for j in range(m + 1): D[0][j] = j # 计算所有 DP 值 for i in range(1, n + 1): for j in range(1, m + 1): if word1[i - 1] != word2[j - 1]: D[i][j]=min(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1]+1) else: D[i][j]=min(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1]) return D[n][m]
这篇关于【力扣72. 编辑距离】dp(Python3)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24Python编程入门指南
- 2024-12-24Python编程基础入门
- 2024-12-24Python编程基础:变量与数据类型
- 2024-12-23使用python部署一个usdt合约,部署自己的usdt稳定币
- 2024-12-20Python编程入门指南
- 2024-12-20Python编程基础与进阶
- 2024-12-19Python基础编程教程
- 2024-12-19python 文件的后缀名是什么 怎么运行一个python文件?-icode9专业技术文章分享
- 2024-12-19使用python 把docx转为pdf文件有哪些方法?-icode9专业技术文章分享
- 2024-12-19python怎么更换换pip的源镜像?-icode9专业技术文章分享