Leetcode-Easy 72. Edit Distance

72. Edit Distance

  • 描述: 求两个字符串的编辑距离
  • 思路: 动态规划
  • 代码
class Solution:
     def  minDistance(self, strWord1, strWord2):
        res = [[0]*(len(strWord2)+1) for _ in range(len(strWord1)+1)]

        # handle extreme conditions first
        res[len(strWord1)][len(strWord2)] = 0

        for j in range(len(strWord2)+1):
            res[len(strWord1)][j] = len(strWord2)-j

        for i in range(len(strWord1)+1):
            res[i][len(strWord2)] = len(strWord1)-i

        for i in range(len(strWord1), -1, -1):
            for j in range(len(strWord2), -1, -1):
                if i == len(strWord1) or j == len(strWord2):
                    continue
                d = 0    
                if strWord1[i]==strWord2[j]:
                    d = res[i+1][j+1]
                else:
                    d = min(res[i][j+1], res[i+1][j], res[i+1][j+1]) + 1 
                res[i][j] = d    

        return res[0][0]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

计算机系统可靠性的计算

计算机系统的可靠性是制从它开始运行(t=0)到某时刻t这段时间内能正常运行的概率,用R(t)表示。 失效率是指单位时间内失效的元件数与元件总数的比例,以λ表示。...

19290
来自专栏GIS讲堂

js+css实现模态层效果

在做web前端的时候,有些时候会涉及到模态层,在此提供一种实现思路,希望对大家有用。先贴效果吧:

48140
来自专栏编程坑太多

jQuery对表格的操作示例

18320
来自专栏君赏技术博客

原生支付 SDK 技术回顾

14030
来自专栏desperate633

第九课 汇总数据聚集函数聚集不同的值

9020
来自专栏IMWeb前端团队

3分钟13行代码搭建sass版移动端网格系统

本文作者:IMWeb 结一 原文出处:IMWeb社区 未经同意,禁止转载 一般来说,网格系统分为container、row及column三大部分,而c...

22870
来自专栏xingoo, 一个梦想做发明家的程序员

【插件开发】—— 12 GEF入门

什么是GEF?   GEF的英文全称是Graphical Editing Framework,也就是图形化编辑框架。它帮助我们轻松的创建一些模型,并提供...

23690
来自专栏网络

HTML 正文内容提取库 Boilerpipe

Boilerpipe 是一个能从 HTML 中剔除广告和其他附加信息,提取出目标信息(如正文内容、发布时间)的 Java 库。 授权协议:Apache 开发语言...

38360
来自专栏小鹏的专栏

刚开始玩openMP,总结一下遇到的一点小问题。

        首先,VS中设置步骤:         工程属性 —> C/C++ —> language 中的Open MP Suport中选择Yes 就OK...

23290
来自专栏Android点滴积累

Android高效内存1:一张图片占用多少内存

  在做内存优化的时候,我们发现除了解决内存泄露问题,剩下的就只有想办法减少真实的内存占用。而在App中,大部分内存可能被我们图片占用了,所以减少图片的内存占用...

24860

扫码关注云+社区

领取腾讯云代金券