文档章节

Edit Distance 将word1变换为word2最少需要多少次操作

o
 osc_y8yehimr
发布于 2019/03/20 16:41
字数 248
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法:

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

给出 work1="mart" 和 work2="karma"

返回 3


 1 class Solution:
 2     """
 3     @param word1: A string
 4     @param word2: A string
 5     @return: The minimum number of steps.
 6     """
 7     def minDistance(self, word1, word2):
 8         # write your code here
 9         memo = {}
10         return self.helper(word1, 0, word2, 0, memo)
11         
12     def helper(self, word1, i, word2, j, memo):
13         if i == len(word1):
14             return len(word2) - j
15         if j == len(word2):
16             return len(word1) - i
17         if (i, j) in memo:
18             return memo[(i, j)]
19             
20         ans = 0
21         if word1[i] == word2[j]:
22             ans = self.helper(word1, i + 1, word2, j + 1, memo)
23         else:
24             # delete word1[i]
25             # insert word2[j] before word1[i]
26             # change word1[i] into word2[j]
27             ans = 1 + self.helper(word1, i + 1, word2, j, memo)
28             ans = min(ans, 1 + self.helper(word1, i, word2, j + 1, memo))
29             ans = min(ans, 1 + self.helper(word1, i + 1, word2, j + 1, memo))
30             
31         memo[(i, j)] = ans
32         
33         return ans

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode 72. 编辑距离

https://leetcode-cn.com/problems/edit-distance/ 72. 编辑距离 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插...

阿豪boy
2019/10/06
0
0
Leetcode: NO.72 编辑距离

题目 链接:https://leetcode-cn.com/problems/edit-distance 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: ...

osc_wfhwwd4t
04/07
14
0
Leetcode: NO.72 编辑距离

题目 链接:https://leetcode-cn.com/problems/edit-distance 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: ...

泛泛之素
04/06
0
0
Leetcode: NO.72 编辑距离

题目 链接:https://leetcode-cn.com/problems/edit-distance 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: ...

osc_npw5uz1o
04/07
13
0
动态规划8: 单词最小编辑距离

给定两个单词,word1, word2, 可以对单词进行insert, delete, replace操作,但每次只能操作一个字符,问最少经过多少步可以将word1修改为word2. 如 word1: horse, word2: rose. 需要对word1...

RichardBillion
2019/08/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-11

更新时间: 2020-07-11 01:01 Disabling Google 2FA Doesn't Need 2FA - (infoq.com) 禁用google2fa不需要2FA 得分:98 | 评论:33 Rackspace S-1 - (sec.gov) 机架空间S-1 得分:59 | 评论:20 S......

FalconChen
今天
142
0
是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
29
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
20
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部