定義：兩個字串之間堵漱，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)综慎，如果它們的距離越大，說明它們越是不同怔锌。許可的編輯操作包括將一個字符替換成另一個字符寥粹，插入一個字符变过，刪除一個字符。
作用：比較兩個字符串的相似度
算法步驟：
1.str1或str2的長度為0返回另一個字符串的長度涝涤。
2.初始化(n+1) * (m+1)的矩陣d，并讓第一行和列的值從0開始增長阔拳。掃描兩字符串（n * m級的）崭孤，如果：str1[i] == str2[j]，用temp記錄它糊肠，為0辨宠。否則temp記為1。然后在矩陣d[i,j]賦于d[i-1,j]+1 货裹、d[i,j-1]+1嗤形、d[i-1,j-1]+temp三者的最小值。
3.掃描完后弧圆，返回矩陣的最后一個值d[n][m]即是它們的距離赋兵。
舉例：str1和str2分別為“ivan1”和“ivan2”
1、第一行和第一列的值從0開始增長
2搔预、舉證元素的產(chǎn)生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t 三者當(dāng)中的最小值
3霹期、依次類推直到矩陣全部生成
python實(shí)現(xiàn)：
def EditDistance(str1, str2):
len1 = len(str1)
len2 = len(str2)
if len1 == 0:
return len2
elif len2 == 0:
return len1
# 矩陣初始化
array = [[0 for _ in range(len1+1)] for _ in range(len2+1)]
for i in range(len1+1):
array[0][i] = i
for i in range(len2+1):
array[i][0] = i
for i in range(1, len2+1):
for j in range(1, len1+1):
if str1[i-1] == str2[j-1]:
temp = 0
else:
temp = 1
array[i][j] = min(array[i-1][j]+1, array[i][j-1]+1, array[i-1][j-1]+temp)
return array[len2][len1]
