面试一生之敌之编辑距离的实现

Posted on | In | |

什么是编辑距离？

最小编辑距离即从一个字符串到另一个字符串所需要的最小编辑次数,利用编辑距离可以判断两个字符串的相似程度。在这里定义的单字符编辑操作有且仅有三种：

  • 插入（Insertion）
  • 删除（Deletion）
  • 替换（Substitution）

假设存在两个字符串X和Y，长度分别为N和M。

  • dp[i][j]为X[1…i]到Y[1…j]的最小编辑距离；
  • X[1…i]表示字符串X的前i个字符；
  • Y[1…j]表示字符串Y的前j个字符；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def Levenshtein_Distance(str1, str2):
    """
    计算字符串 str1 和 str2 的编辑距离
    :param str1
    :param str2
    :return:
    """
    n,m = len(str1),len(str2)
    #根据dp[i][j]定义初始化dp
    matrix = [[ i + j for j in range(m + 1)] for i in range(n + 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)]