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 面向对象 成员的访问约束

在Python中是通过一套命名体系来识别成约的访问范围的 class MyObjec(object): username = "developerworks" # public _ema...

python3+PyQt5自定义视图详解

python3+PyQt5自定义视图详解

pyqt提供的几个视图类都可以较好工作,包括QLisView,QTableView和QTreeView。但是对于一些难以用现有的方式来呈现数据,这时,可以创建我们自己的视图子类并将其用做...

Python编程中NotImplementedError的使用方法

Python编程中raise可以实现报出错误的功能,而报错的条件可以由程序员自己去定制。在面向对象编程中,可以先预留一个方法接口不实现,在其子类中实现。 如果要求其子类一定要实现,不实现...

Django中的“惰性翻译”方法的相关使用

使用 django.utils.translation.gettext_lazy() 函数,使得其中的值只有在访问时才会被翻译,而不是在 gettext_lazy() 被调用时翻译。 例...

Python创建二维数组实例(关于list的一个小坑)

0.目录 1.遇到的问题 2.创建二维数组的办法 •3.1 直接创建法 •3.2 列表生成式法 •3.3 使用模块numpy创建 1.遇到的问题 今天...