Python 动态规划算法,计算单词距离，python算法,[Python]代码#!

Python 动态规划算法,计算单词距离，python算法,[Python]代码#!

[Python]代码

#!/usr/bin/env python#coding=utf-8def 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 doctestdoctest.testmod()raw_input("Success!")