数据结构与算法之最短编辑距离

最短编辑距离是指从一个字符串转换成另一个字符串所需要的最少操作次数。这些操作可以是插入、删除和替换字符。

最短编辑距离可以用来解决很多问题，比如拼写纠错、字符串相似度计算、语音识别等等。

最短编辑距离的原理可以通过动态规划来实现。我们可以定义一个二维数组dp，其中dp[i][j]表示把字符串s1的前i个字符转换成字符串s2的前j个字符所需的最少操作次数。

然后，我们可以考虑对字符串s1进行以下操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

对于第一种情况，我们需要对字符串s1进行插入操作，然后将dp[i][j]的值更新为dp[i][j-1]+1，表示将s1中的一个字符插入到s2的第j个位置上所需的最少操作次数。

对于第二种情况，我们需要对字符串s1进行删除操作，然后将dp[i][j]的值更新为dp[i-1][j]+1，表示将s1中的一个字符删除所需的最少操作次数。

对于第三种情况，我们需要对字符串s1进行替换操作，然后将dp[i][j]的值更新为dp[i-1][j-1]+1，表示将s1中的一个字符替换为s2中的一个字符所需的最少操作次数。

最后，我们可以通过dp[s1.length()][s2.length()]来获取s1转换成s2所需的最少操作次数。

总之，最短编辑距离是一种非常有用的算法，可以帮助我们解决很多字符串相关的问题。

一、C 实现 最短编辑距离 及代码详解

最短编辑距离，也称为Levenshtein距离或编辑距离，是指将一个字符串转换成另一个字符串所需的最少操作次数。操作包括插入一个字符、删除一个字符、替换一个字符。

C语言实现最短编辑距离的算法如下：

#include <stdio.h>
#include <string.h>
#define MAXLEN 100

int min(int a, int b, int c) {
    
    if (a < b && a < c) return a;
    else if (b < a && b < c) return b;
    else return c; 
}

int lev_distance(char *s1, char *s2) {
   
    int m = strlen(s1), n = strlen(s2), i, j;
    int D[MAXLEN][MAXLEN];
    for (i = 0; i <= m; i++) D[i][0] = i;
    for (j = 0; j <= n; j++) D[0][j] = j;
    for (i = 1; i <= m; i++) {
   
        for (j = 1; j <= n; j++) {
   
            if (s1[i-1] == s2[j-1]) D[i][j