Python基于動(dòng)態(tài)規(guī)劃算法計(jì)算單詞距離

#!/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 .
 動(dòng)態(tài)規(guī)劃算法,計(jì)算單詞距離
 >>> 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!")