45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:Python动态规划算法去计算单词距离的方法

Python动态规划算法去计算单词距离的方法

2015-08-11 12:40:40 来源:www.45fan.com 【

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程序设计有所帮助。


本文地址:http://www.45fan.com/a/question/17412.html
Tags: python 基于 动态规划
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部