字符串的编辑距离：莱文斯坦距离的递归与动态规划实现

编辑距离，说白了就是衡量两个字符串有多「像」的一个指标。我当年第一次接触这个概念时，是在做一个拼写纠错系统。用户输入「appple」，系统要猜出他大概率想打的是「apple」还是「apply」。嗯，这时候编辑距离就派上用场了。

莱文斯坦距离（Levenshtein Distance）是最常见的一种编辑距离。它定义了从一个字符串变成另一个字符串，最少需要多少次「编辑操作」。操作只有三种：插入一个字符、删除一个字符、替换一个字符。

核心思想：三步操作

假设我们要把字符串 A 变成字符串 B。每次操作只能动一个字符。举个例子：

• 插入：在「ab」中插入「c」，得到「acb」
• 删除：在「abc」中删除「b」，得到「ac」
• 替换：在「abc」中把「b」换成「d」，得到「adc」

你想想看，这其实很像我们平时改错别字的过程。我写代码时经常把变量名拼错，然后手动改回来——本质上就是在做编辑距离的计算。

递归实现：最直观的思路

递归的思路其实很朴素。我们从两个字符串的末尾开始比较：

int min(int a, int b, int c) {
    int min = a < b ? a : b;
    return min < c ? min : c;
}

int levenshtein_recursive(char *s1, char *s2, int m, int n) {
    // 如果其中一个字符串为空，距离就是另一个的长度
    if (m == 0) return n;
    if (n == 0) return m;
    
    // 如果最后一个字符相同，不需要操作
    if (s1[m-1] == s2[n-1]) {
        return levenshtein_recursive(s1, s2, m-1, n-1);
    }
    
    // 否则，取三种操作的最小值 + 1
    return 1 + min(
        levenshtein_recursive(s1, s2, m, n-1),   // 插入
        levenshtein_recursive(s1, s2, m-1, n),   // 删除
        levenshtein_recursive(s1, s2, m-1, n-1)  // 替换
    );
}

这段代码逻辑上完全正确。但有个问题——效率极低。为什么？因为递归会重复计算大量子问题。比如计算「abc」和「def」的距离，它会反复计算「ab」和「de」的距离很多次。时间复杂度是指数级的，O(3^n)。

动态规划：把重复计算干掉

动态规划的思路很简单：把中间结果存起来，避免重复计算。我们用一个二维数组 dp[i][j] 表示 s1 的前 i 个字符到 s2 的前 j 个字符的编辑距离。

int levenshtein_dp(char *s1, char *s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    int dp[m+1][n+1];
    
    // 初始化边界
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    // 填表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                int insert = dp[i][j-1];
                int delete = dp[i-1][j];
                int replace = dp[i-1][j-1];
                dp[i][j] = 1 + min(insert, delete, replace);
            }
        }
    }
    
    return dp[m][n];
}

这个版本的时间复杂度是 O(m*n)，空间复杂度也是 O(m*n)。对于大部分实际场景，这已经够用了。

状态转移表：一眼看懂

我习惯画个表来理解这个过程。比如计算「kitten」到「sitting」的距离：

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

右下角的值 3，就是「kitten」到「sitting」的编辑距离。你看，替换 k→s，替换 e→i，插入 g，正好三步。

空间优化：滚动数组

其实我们不需要整个二维数组。因为 dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 这三个值。所以用两行就够了。

int levenshtein_optimized(char *s1, char *s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    int prev[n+1], curr[n+1];
    
    for (int j = 0; j <= n; j++) prev[j] = j;
    
    for (int i = 1; i <= m; i++) {
        curr[0] = i;
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                curr[j] = prev[j-1];
            } else {
                int insert = curr[j-1];
                int delete = prev[j];
                int replace = prev[j-1];
                curr[j] = 1 + min(insert, delete, replace);
            }
        }
        // 交换行
        int *temp = prev;
        prev = curr;
        curr = temp;
    }
    
    return prev[n];
}

空间复杂度降到了 O(n)。我个人习惯在嵌入式或内存受限的场景下用这个版本。

知识体系图

编辑距离的应用远不止拼写纠错。我在做基因序列比对时也用过它——DNA 序列本质上就是由 A、T、C、G 组成的字符串，编辑距离可以衡量两条基因序列的相似度。还有抄袭检测、语音识别中的候选词排序，背后都有它的影子。

嗯，今天就先聊到这里。代码你拿去跑一跑，试试「kitten」和「sitting」，看看结果是不是 3。动手实践永远是最好的学习方式。

---

公众号：蓝海资料掘金营，微信 deep3321