[代码] [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!")
|
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
评论(0)