字符串编辑距离-edit distance of two strings

发表于 | 分类于

问题

给2个字符串str1和str2. 通过对单个字符进行插入、删除或替换的方式将str1变换为str2的最小操作次数，定义为编辑距离。

输入任意字符串str1和str2，输出将str1变换为str2的编辑距离。

LeetCode：72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Jupyter notebook: edit distance of two strings


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def editDistance(str1,str2):
    #异常处理
    if str1 is None or str2 is None:
        return -1 
    m,n = len(str1),len(str2)
    # 定义编辑距离
    d = [[0]*(n+1) for _ in range(m+1)]
    # 边界条件
    for i in range(1,m):
        d[i][0] = i
    for j in range(1,n):
        d[0][j] = j
    # 迭代过程    
    for i in range(1,m+1):
        for j in range(1,n+1):
            if str1[i-1]==str2[j-1]:
                d[i][j] = d[i-1][j-1]
            else:
                d[i][j] = min(d[i][j-1]+1,    # 插入
                              d[i-1][j]+1,    # 删除
                              d[i-1][j-1]+1)  # 替换
    return d[-1][-1]

测试

1
2
3
str1 ='cat'
str2 = 'mouse'
editDistance(str1,str2)

Out: 3


分析

使用动态规划(dynamic programming,DP)，一般DP有两个过程：确定迭代公式和确定边界条件

确定迭代公式

d[i][j]表示str1[0:i]与str2[0:j]之间的编辑距离，

str1[0:i]不包含指标(index)为i的字符。如果str1='insert', 则str1[0:3]='ins'

假设已计算出$\{d[p][q]: 0 \le p \le (i-1),0 \le q \le (j-1) \}​$。有如下两种情况：

  1. 当前字符相等：str1[i-1]==str2[j-1]

此时，只需要将字符串str1[0:i-1]转换成str2[0:j-1], 即

d[i][j]=d[i-1][j-1]

比如 $ mouse_{i-1} t\rightarrow mouse_{j-1} \Rightarrow mous_{i-2} \rightarrow mous_{j-2} ​$

  1. 当前字符不等​：str1[i-1]!=str2[j-1]

此时，就需要使用插入、删除或替换的方式处理

比如问题是 $ mouse_{i-1} \rightarrow cat_{j-1}​$

  • 插入: 在$e_{i-1}$后插入一个$t$, 问题转化为 $ mouse_{i-1} t\rightarrow cat_{j-1} \Rightarrow mouse_{i-1} \rightarrow ca_{j-2} $

从而：d[i][j]=d[i][j-1]+1

插入1次，$ mouse_{i-1} ​$修改为$ca_{j-2}​$修改d[i][j-1]次

  • 删除：删除$e_{i-1}$，问题转化为$ mous_{i-2} \rightarrow cat_{j-1}$

从而：d[i][j]=d[i-1][j]+1

删除1次，$ mous_{i-2} $修改为$cat_{j-1}$修改d[i-1][j]次

  • 替换：把 $e_{i-1}$替换为$t$, 问题转化为 $ moust_{i-1} \rightarrow cat_{j-1} \Rightarrow mous_{i-2} \rightarrow ca_{j-2} $

从而: d[i][j]=d[i-1][j-1]+1

替换1次，$ mous_{i-2} $修改为$ca_{j-2}$修改d[i-1][j-1]次

第2种情况下，d[i][j]取d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+1中最小值。

d[i][j] = min(d[i-1][j]+1,d[i-1][j-1]+1,d[i][j-1]+1)


边界条件

当str1=' '时，使用插入将str1变换为str2, d[0][j]=j

' '变为 cat, 编辑次数为3次

当str2=' '时，使用删除将str1变换为str2, d[i][0]=i

mouse变为' ',编辑次数5次