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基于回溯法子集树模板解决0-1背包问题实例
• Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例
• Python二叉树的定义及常用遍历算法分析
• Python基于贪心算法解决背包问题示例
• 动态规划之矩阵连乘问题Python实现方法
• Python用户推荐系统曼哈顿算法实现完整代码
• Python实现调度算法代码详解
• Python实现字符串匹配算法代码示例
• 详解K-means算法在Python中的实现
• Python机器学习之决策树算法实例详解
• Python基于动态规划算法解决01背包问题实例