LeetCode题解(0583):删除两个字符串的字符直至两字符串相等的操作次数(Python)
发布日期:2021-06-29 19:58:00
浏览次数:3
分类:技术文章
本文共 2331 字,大约阅读时间需要 7 分钟。
题目:(中等)
标签:字符串、动态规划、动态规划-状态表格
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( M × N ) O(M×N) O(M×N) | O ( M × N ) O(M×N) O(M×N) | 300ms (77.17%) |
Ans 2 (Python) | O ( M × N ) O(M×N) O(M×N) | O ( N ) O(N) O(N) | 272ms (97.02%) |
Ans 3 (Python) | O ( M × N ) O(M×N) O(M×N) | O ( N ) O(N) O(N) | 256ms (99.26%) |
LeetCode的Python执行用时随缘,只要时间复杂度没有明显差异,执行用时一般都在同一个量级,仅作参考意义。
解法一(动态规划):
class Solution: def minDistance(self, word1: str, word2: str) -> int: # 生成状态表格 N1, N2 = len(word1), len(word2) matrix = [[0] * (N1 + 1) for _ in range(N2 + 1)] # 填写首行首列 for j in range(1, N1 + 1): matrix[0][j] = matrix[0][j - 1] + 1 for i in range(1, N2 + 1): matrix[i][0] = matrix[i - 1][0] + 1 # 状态计算 for i in range(1, N2 + 1): for j in range(1, N1 + 1): if word2[i - 1] != word1[j - 1]: matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + 1 else: matrix[i][j] = matrix[i - 1][j - 1] return matrix[-1][-1]
解法二(单行动态规划):
class Solution: def minDistance(self, word1: str, word2: str) -> int: # 生成状态表格 N1, N2 = len(word1), len(word2) matrix = [0] * (N1 + 1) # 填写首行首列 for j in range(1, N1 + 1): matrix[j] = matrix[j - 1] + 1 # 状态计算 for i in range(1, N2 + 1): last = matrix[0] matrix[0] += 1 for j in range(1, N1 + 1): tmp = matrix[j] if word2[i - 1] != word1[j - 1]: matrix[j] = min(matrix[j], matrix[j - 1]) + 1 else: matrix[j] = last last = tmp return matrix[-1]
解法三(计算相同子序列):
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gcONmcxT-1597633134346)(LeetCode题解(0583)]:截图1.png)
class Solution: def minDistance(self, word1: str, word2: str) -> int: # 生成状态表格 N1, N2 = len(word1), len(word2) matrix = [0] * (N1 + 1) # 状态计算 for i in range(1, N2 + 1): last = 0 for j in range(1, N1 + 1): tmp = matrix[j] if word2[i - 1] == word1[j - 1]: matrix[j] = last + 1 else: matrix[j] = max(matrix[j], matrix[j - 1]) last = tmp # 生成结果 return N1 + N2 - 2 * matrix[-1]
转载地址:https://dataartist.blog.csdn.net/article/details/108051563 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月29日 20时44分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Qt拖放
2019-04-30
Qt图片拖放
2019-04-30
android库模块直接依赖时不能重复嵌套依赖
2019-04-30
关于SDK回调Qt函数的问题
2019-04-30
查询linux系统中空闲内存/内存使用状态查看/剩余内存查看
2019-04-30
Linux下屏保设置
2019-04-30
使用开源软件OpenIPMI来监控服务器温度
2019-04-30
使用IPMI管理Linux服务器
2019-04-30
使用ipmi进行服务器管理
2019-04-30
基于Linux的嵌入式系统全程喂狗策略
2019-04-30
linux嵌入式系统开发之看门狗----应用篇。
2019-04-30
看门狗用户空间程序(可用来检测服务器死机)
2019-04-30
scp 使用方法
2019-04-30
Linux man命令的使用方法
2019-04-30
shell高效获取分割字符串的方法?
2019-04-30
Linux Shell编程变量赋值和引用
2019-04-30
计算机专业推荐书籍
2019-04-30
程序员的成长之路
2019-04-30
linux下CPU温度监测
2019-04-30
java数组查找元素索引,无需排序
2019-04-30