[代码] [Python]代码
01 |
#!/usr/bin/env python |
02 |
#coding=utf-8 |
03 |
04 |
def word_distance(m,n):
|
05 |
"""compute the least steps number to convert m to n by insert , delete , replace .
|
06 |
动态规划算法,计算单词距离
|
07 |
>>> print word_distance("abc","abec")
|
08 |
1
|
09 |
>>> print word_distance("ababec","abc")
|
10 |
3
|
11 |
"""
|
12 |
len_1=lambda x:len(x)+1
|
13 |
14 |
c=[[i] for i in range(0,len_1(m)) ]
|
15 |
c[0]=[j for j in range(0,len_1(n))]
|
16 |
17 |
for i in range(0,len(m)):
|
18 |
# print i,' ',
|
19 |
for j in range(0,len(n)):
|
20 |
c[i+1].append(
|
21 |
min(
|
22 |
c[i][j+1]+1,#插入n[j]
|
23 |
c[i+1][j]+1,#删除m[j]
|
24 |
c[i][j] + (0 if m[i]==n[j] else 1 )#改
|
25 |
)
|
26 |
)
|
27 |
# print c[i+1][j+1],m[i],n[j],' ',
|
28 |
# print ''
|
29 |
return c[-1][-1]
|
30 |
31 |
import doctest
|
32 |
doctest.testmod() |
33 |
raw_input("Success!")
|