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利用带权重随机数解决抽奖和游戏爆装备问题

Python利用带权重随机数解决抽奖和游戏爆装备问题

关于带权随机数 为了帮助理解,先来看三类随机问题的对比: 1.已有n条记录,从中选取m条记录,选取出来的记录前后顺序不管。 实现思路:按行遍历所有记录,约隔n/m条取一个数据即可 2.在...

Python读写Json涉及到中文的处理方法

今天在帮前端准备数据的时候,需要把数据格式转成json格式,说实话,涉及到中文有时候真的是很蛋疼,除非对Python的编码规则比较了解,不然处理起来真的很蛋疼。 整个逻辑 我们需要处理的...

python文件操作的简单方法总结

文件操作1 #文件操作流程:1、打开文件,得到一个文件句柄;通过文件句柄操作文件;关闭文件。 #将文件打开文件赋给file1,test_file为文件名,utf-8为文件编码;fil...

Python学习笔记之While循环用法分析

本文实例讲述了Python学习笔记之While循环用法。分享给大家供大家参考,具体如下: 前面一篇《Python学习笔记之For循环用法》详细介绍了Python for循环,这里再来讲述...

解决Python pandas df 写入excel 出现的问题

解决Python pandas df 写入excel 出现的问题

学习Python数据分析挖掘实战一书时,在数据预处理阶段,有一节要使用拉格朗日插值法对缺失值补充,代码如下: #-*- coding:utf-8 -*- import pandas...