• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

动态规划算法,计算单词距离

python 水墨上仙 1741次浏览

动态规划算法,计算单词距离


#!/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!") 


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明动态规划算法,计算单词距离
喜欢 (0)
加载中……