Python基于动态规划算法计算单词距离

yipeiwu_com6年前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使用MONGODB入门实例

本文实例讲述了Python使用MONGODB的方法。分享给大家供大家参考。具体如下: 1. 启动mongodb mongod --dbpath d:\db 2. 启动为系统应用...

Python学习笔记之pandas索引列、过滤、分组、求和功能示例

本文实例讲述了Python学习笔记之pandas索引列、过滤、分组、求和功能。分享给大家供大家参考,具体如下: 解析html内容,保存为csv文件 /post/162401.htm 前面...

老生常谈python的私有公有属性(必看篇)

python中,类内方法外的变量叫属性,类内方法内的变量叫字段。他们的私有公有访问方法类似。 class C: __name="私有属性" def func(self):...

Python清空文件并替换内容的实例

有个文本文件,需要替换里面的一个词,用python来完成,我是这样写的: def modify_text(): with open('test.txt', "r+") as f:...

python实现登陆知乎获得个人收藏并保存为word文件

这个程序其实很早之前就完成了,一直没有发出了,趁着最近不是很忙就分享给大家. 使用BeautifulSoup模块和urllib2模块实现,然后保存成word是使用python docx模...