计算文本间距的实现_c++获取两行文本之间的间距

我们可以使用动态规划的方式来计算文本间距，通过建立DP数组将对比文本的问题分成多个子问题:
文本间的间距通常包含以下三种情况：
insert： abc -> abdc
remove: abc -> ab
update: abc -> adc
我们只需要计算不同情况下最短间距就可以了，具体实现方式如下：

def text_distance(str1, str2):
    m, n = len(str1), len(str2)

    # 构建二维数组来存储子问题的答案
    dp = [[0 for x in range(n+1)] for x in range(m+1)]

    # 利用动态规划算法，填充数组
    for i in range(m+1):
        for j in range(n+1):

            # 假设第一个字符串为空，则转换的代价为j(j次的插入)
            if i == 0:
                dp[i][j] = j

            # 同样，假设第二个字符串为空，则转换的代价为i(i次的插入)
            elif j == 0:
                dp[i][j] = i

            # 如果最后一个字符相等，就不会产生代价
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]

            # 如果最后一个字符不一样，则考虑多种可能性，并且选择其中的最小值
            else:
                dp[i][j] = 1 + min(dp[i][j-1],      # Insert
                                  dp[i-1][j],       # Remove
                                  dp[i-1][j-1])     # Replace
    return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

我们可以验证一下

text_distance('go', 'going')     # output:3
text_distance('whose', 'who')     # output:2
text_distance('who', 'how')     # output:2
1
2
3