第三节 编辑距离 edit distance 精通C语言 递归算法和动态规划

 第三节 编辑距离 edit distance

第一节 序 斐波那契数列         Fibonacci

第二节 0 1背包问题   0 1 Knapsack Problem

第三节 编辑距离         edit distance

第四节 子集总和         subset sum

第五节 钢条切割          cut rod

第六节 硬币找零          Coin Change

第七节 最长公共子序列         Longest Common Subsequence

第八节 矩阵链式乘法 Matrix Chain Multiplication

第九节 最优游戏策略 Optimal Strategy for a Game

第十节 最优二叉查找树         Optimal Binary Search Tree

第十一节 最长递增子序列 Longest Increasing Subsequence

问题描述

有两个字符串src和dest,通过对字符串进行最少的编辑操作将src转换为dest。

1.insert

2.remove

3.replace

以上所有操作花费均相等。

递归解决方案

从两个字符串的左侧或右侧开始处理所有字符。我们从右侧向左遍历，遍历每对字符有两种可能性。

m: Length of str1 (src string)

n: Length of str2 (dest string)

1.如果两个字符串的最后一个字符相同，则无事可做。忽略最后一个字符并获得剩余字符串的计数。因此，我们将递归长度同时减1变为m-1和n-1。

2.否则（如果最后一个字符不同），我们考虑对“ str1”的所有操作，考虑对第一个字符串的最后一个字符的所有三个操作，递归计算所有三个操作的最小开销，并取三个值中的最小值。

1.insert: Recur for m and n-1

2.remove: Recur for m-1 and n

3.replace: Recur for m-1 and n-1

该解决方案的时间复杂度,最坏情况下 O(3^m).

int min(int x, int y, int z) { int t = (x < y)? x : y; return (t < z)? t : z; }

int editdist (char *s1, char *s2, int n1, int n2)

{

    if (n1 == 0)

        return n2;

    if (n2 == 0)

        return n1;

    if (s1[n1-1] == s2[n2-1])

        return editdist(s1, s2, n1-1, n2-1);

    else

        return 1 + min(editdist(s1, s2, n1, n2-1),      //insert            

                        editdist(s1, s2, n1-1, n2),     //remove

                        editdist(s1, s2, n1-1, n2-1)); //replace

}

DP解决方案

使用自下而上的DP可以最佳地解决此问题。我们将首先计算将字符串src的前缀转换为字符串dest的前缀所需的最少操作。然后，我们将使用此信息来计算最小编号索引，将src的较大前缀转换为dest的较大前缀所需的操作数。

该解决方案的时间复杂度将为O(m*n)。

int editdist (char *s1, char *s2, int n1, int n2)

{

    int dp[n1+1][n2+1];

    int i, j;

    for (i = 0; i < n1+1; i++)

    {

        for (j = 0; j < n2+1; j++)

        {

            if (i == 0)

                dp[i][j] = j;

            else if (j == 0)

                dp[i][j] = i;

            else if (s1[i-1] == s2[j-1])

                dp[i][j] = dp[i-1][j-1];

            else

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

        }

    }

    return dp[n1][n2];

}