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

yipeiwu_com5年前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读取目录下所有的jpg文件,并显示第一张图片的示例

如下所示: # -*- coding: UTF-8 -*- import numpy as np import os from scipy.misc import imread, i...

python实现DNS正向查询、反向查询的例子

1.DNS查询过程: 以查询 www.baidu.com为例 (1)电脑向本地域名服务器发送解析www.baidu.com的请求(2)本地域名服务器收到请求后,先查询本地的缓存,如果找到...

Python_LDA实现方法详解

LDA(Latent Dirichlet allocation)模型是一种常用而用途广泛地概率主题模型。其实现一般通过Variational inference和Gibbs Sampin...

python将pandas datarame保存为txt文件的实例

CSV means Comma Separated Values. It is plain text (ansi). The CSV ("Comma Separated Value")...

python的类方法和静态方法

本文实例讲述了python的类方法和静态方法。分享给大家供大家参考。具体分析如下: python没有和C++中static关键字,它的静态方法是怎样的呢?还有其它语言中少有的类方法又是神...