编辑距离

编辑距离（也叫Levenshtein距离）是两个字符串之间通过字符编辑相互转化所需要的最小操作次数。

字符编辑是指单个字符的删除、插入和替换这三种操作。

例如把单词shine转换为单词train最少需要四次操作，以下就是一种可行的方案:

                shine → shin (删除'e')
                shin  → tshin (插入't')
                tshin → trhin (将's'替换为'r')
                trhin → train (将'h'替换'a')

对给定的每对单词，输出两者间的编辑距离，每条数据一行。

本题难度:

解答

动态规划的标准例题之一，此处使用的Leetcode的例题代码。

最终代码有九行。

代码长度：248字节 vs. 全站第一：90字节。

import sys
for a in sys.argv[1:]:
 m=a.find(' ')+1
 n=len(a)-m+1
 d=[[max(i,j)for j in range(n)]for i in range(m)]
 for i in range(1,m):
  for j in range(1,n):
   d[i][j]=min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(a[i-1]!=a[m+j-1]))
 print(d[-1][-1])