Python基于动态规划算法计算单词距离
作者:Sephiroth 时间:2021-09-18 11:18:16
本文实例讲述了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程序设计有所帮助。
标签:Python,算法
0
投稿
猜你喜欢
python垃圾回收机制(GC)原理解析
2023-01-05 10:57:46
javascript操作ASP.NET服务器控件
2023-07-21 15:09:26
牛刀小试YUI compressor(YUI安装方法)
2009-02-12 16:18:00
pycharm运行出现ImportError:No module named的解决方法
2022-09-10 18:06:23
什么是UE,UED?
2008-07-24 13:26:00
为导入文件加上时间戳标记的两种方法
2009-01-07 14:14:00
Python网络编程 Python套接字编程
2022-06-09 09:41:32
关于Python下载大文件时哪种方式速度更快
2021-03-15 05:46:37
Python的Flask项目中获取请求用户IP地址 addr问题
2021-09-08 08:38:47
python定向爬取淘宝商品价格
2023-10-03 23:33:12
Python利用format函数实现对齐打印(左对齐、右对齐与居中对齐)
2021-07-30 05:16:16
linux下安装php扩展memcache的方法
2023-11-21 19:49:02
十分钟轻松掌握dataframe数据选择
2021-03-03 11:11:40
Python使用Flask Migrate模块迁移数据库
2023-08-10 09:17:30
Python干货:分享Python绘制六种可视化图表
2023-07-10 10:01:03
php日期转时间戳,指定日期转换成时间戳
2023-06-20 17:02:23
js放大缩小容器:仿动画
2008-02-15 11:34:00
javascript 版 Bad Apple 字符动画
2010-01-28 12:19:00
asp使用XMLHTTP下载远程数据输出到浏览器
2007-11-04 10:34:00
Python生成词云的实现代码
2023-09-12 22:42:48