Python基于动态规划算法计算单词距离,python算法
Python基于动态规划算法计算单词距离,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程序设计有所帮助。
相关内容
- Python计算已经过去多少个周末的方法,python已经过去
- 详解Python的Django框架中的中间件,pythondjango
- Python字符串转换成浮点数函数分享,python点数
- 通过mod_python配置运行在Apache上的Django框架,mod_pythond
- 在Django的上下文中设置变量的方法,django上下文
- Python简单调用MySQL存储过程并获得返回值的方法,pyth
- 在Django框架中运行Python应用全攻略,djangopython
- Python实现SVN的目录周期性备份实例,pythonsvn
- Python中max函数用法实例分析,python实例分析
- Python通过正则表达式选取callback的方法,pythoncallback
评论关闭