Python基于动态规划算法计算单词距离
作者：Sephiroth 发布时间：2021-09-18 11:18:16
标签：Python,算法
本文实例讲述了Python基于动态规划算法计算单词距离。分享给大家供大家参考。具体如下：
#!/usr/bin/env python
#coding=utf-8
def word_distance(m,n):
"""compute the least steps number to convert m to n by insert , delete , replace .
动态规划算法,计算单词距离
>>> print word_distance("abc","abec")
1
>>> print word_distance("ababec","abc")
3
"""
len_1=lambda x:len(x)+1
c=[[i] for i in range(0,len_1(m)) ]
c[0]=[j for j in range(0,len_1(n))]
for i in range(0,len(m)):
# print i,' ',
for j in range(0,len(n)):
c[i+1].append(
min(
c[i][j+1]+1,#插入n[j]
c[i+1][j]+1,#删除m[j]
c[i][j] + (0 if m[i]==n[j] else 1 )#改
)
)
# print c[i+1][j+1],m[i],n[j],' ',
# print ''
return c[-1][-1]
import doctest
doctest.testmod()
raw_input("Success!")
希望本文所述对大家的Python程序设计有所帮助。
0
投稿猜你喜欢
- 三、支持XML的公司和它们的开发工具 尽管XML还处在开发阶段，其标准正在由W3C组织制定，但是已经有许多公司表示全力支持XML，并开发了不
- 题目描述给定一个只包括 '(',')','{','}','['
- 关于建立索引的几个准则：1、合理的建立索引能够加速数据读取效率，不合理的建立索引反而会拖慢数据库的响应速度。2、索引越多，更新数据的速度越慢
人们对于产品设计这类事情，往往容易眼高手低，在宇宙层面上夸夸其谈，却落不了地，只能飘着。真正到了自己动手的时候，才会发现问题很多，实践和理论- 类的特殊成员之call#!/usr/bin/env python# _*_coding:utf-8 _*_class SpecialMemb
- 前言Golang中当程序发生致命异常时（比如数组下标越界，注意这里的异常并不是error），Golang程序会panic（运行时恐慌）。当程
- 小毅的blog：http://andymao.com/andy/注：本文实例在IE5.x下可能会显示不出来，请使用IE6、IE7、Firef
- 一、打开/关闭文件1、对文件操作时首先要打开文件，打开文件用 fopen（）函数，语法是：fopen(filename,mode,inclu
- 本周的豆知识分享就来深入研究一下window.event对象。请先看看下边的代码片断。 <button id=”btn”&g
- 从毕业实习算起，从事可用性方面的工作到现在已经5年了。在此记录笔者的一些所见所想，和大家讨论分享一下。用户研究在“以用户为中心”的界面设计方
- 过滤器模板层对变量的操作实际还有很多，过滤器就是其中一种。学过Linux系统的一定知道管道操作符，其可以将上一步输出直接作为下一步输入进行处
- 思路：使用socket传输文件过程中，如果单次传输每次只能发送一部分数据，如果针对大文件，一次传输肯定是不行的，所以需要我们在传输的时候提前
- Python 中的可变和不可变对象一、文字描述可变和不可变对象在 Python 中，一切皆为对象Python 中不存在值传递，一切传递的都是
- Mcrypt扩展库可以实现加密解密功能，就是既能将明文加密，也可以密文还原。1.PHP加密扩展库Mcrypt安装在标准的PHP安装过程中并没
- 因为外贸网站,禁止同行抄袭，所以防止中国ip访问访问,访问的时候有密码提示,这样的代码如何写.请给一个提示.或者有好的代码,请分享下。 &n
- SELECT表名=case when a.colorder=1 then d.name else '' end,表说明=ca
- 今天编ZBlog上传模块的时候，需要用到一个提取文章中文件名的子程，开始我把问题想复杂了，匹配了所有可能的文件名，不仅正则表达
- 一、类和对象通俗理解：类就是模板，对象就是通过模板创造出来的物体类(Class)由3个部分构成：类的名称: 类名类的属性: 一组数据类的方法
- Python time模块时间获取和转换Time模块介绍Python的Time库可以进行时间相关的处理，如访问当前日期和时间，输出不同格式的
- 举个例子吧Django最佳实践与部署：Nginx + Gunicorn + Supervisor（Ubuntu和CentOS）http://
