由动态规划计算编辑距离引发的思考

旧城等待， 2022-05-15 04:55 376阅读 0赞

# 简单介绍 #

编辑距离算法：  
[https://www.cnblogs.com/BlackStorm/p/5400809.html][https_www.cnblogs.com_BlackStorm_p_5400809.html]  
[https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/05.02.html][https_wizardforcel.gitbooks.io_the-art-of-programming-by-july_content_05.02.html]  
[https://www.dreamxu.com/books/dsa/dp/edit-distance.html][https_www.dreamxu.com_books_dsa_dp_edit-distance.html] 详细

# c语言实现 #

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using std::min;
    int lena, lenb;
    char a[1010], b[1010];
    void read() {
        scanf("%s%s", a, b);
        lena = strlen(a);
        lenb = strlen(b);
    }
    
    int dp[1010][1010];
    
    int min_of_three(int a, int b, int c)
    {
            int tmp = a < b ? a : b;
            return c < tmp ? c : tmp;
    }
    
    //一维数组
    int edit_distance(char *a, char *b)
    {
        int lena = strlen(a);
        int lenb = strlen(b);
        int d[lenb+1];
        int i, j, old, temp;
    
        for (j = 0; j <= lenb; j++) {
            d[j] = j;
        }
    
        for (i = 1; i <= lena; i++) {
            old = i - 1;
            d[0] = i;
            for (j = 1; j <= lenb; j++) {
                temp = d[j];
                // 算法中 a, b 字符串下标从 1 开始，c 语言从 0 开始，所以 -1
                if (a[i-1] == b[j-1]) {
                    d[j] = old;
                } else {
                    d[j] = min_of_three(d[j] + 1, d[j-1] + 1, old + 1);
                }
                old = temp;
            }
        }
        return d[lenb];
    }
    
    // 二维数组
    void work() {
        for(int i=1; i<=lena; i++) dp[i][0] = i;
        for(int j=1; j<=lenb; j++) dp[0][j] = j;
        for(int i=1; i<=lena; i++)
            for(int j=1; j<=lenb; j++)
                if(a[i-1]==b[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1;
        printf("%d\n", dp[lena][lenb]);
    }
    
    int main() {
        read();
        work();
            int len = edit_distance(a, b);
            printf("%d\n", len);
        return 0;
    }

# 参考 #

[一维动态规划及优化(max subarray, sell stock, Climbing Stairs)][max subarray_ sell stock_ Climbing Stairs]  
[背包9讲一个不错的实现方案][9]

[https_www.cnblogs.com_BlackStorm_p_5400809.html]: https://www.cnblogs.com/BlackStorm/p/5400809.html
[https_wizardforcel.gitbooks.io_the-art-of-programming-by-july_content_05.02.html]: https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/05.02.html
[https_www.dreamxu.com_books_dsa_dp_edit-distance.html]: https://www.dreamxu.com/books/dsa/dp/edit-distance.html
[max subarray_ sell stock_ Climbing Stairs]: https://www.jianshu.com/p/62e54802d12c
[9]: https://blog.csdn.net/qq_33850438/article/details/50609473