1. 递归形式:
1 def Levenshtein_Distance_Recursive(str1, str2): 2 3 if len(str1) == 0: 4 return len(str2) 5 elif len(str2) == 0: 6 return len(str1) 7 elif str1 == str2: 8 return 0 9 10 if str1[len(str1)-1] == str2[len(str2)-1]: 11 d = 0 12 else: 13 d = 1 14 15 return min(Levenshtein_Distance_Recursive(str1, str2[:-1]) + 1, 16 Levenshtein_Distance_Recursive(str1[:-1], str2) + 1, 17 Levenshtein_Distance_Recursive(str1[:-1], str2[:-1]) + d)
2. 动态规划形式:
def Levenshtein_Distance(str1, str2): """ 计算字符串 str1 和 str2 的编辑距离 :param str1 :param str2 :return: """ matrix = [[ i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)] for i in range(1, len(str1)+1): for j in range(1, len(str2)+1): if(str1[i-1] == str2[j-1]): d = 0 else: d = 1 matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d) return matrix[len(str1)][len(str2)]