以最短路径将一个字符串转换为另一个字符串

Question

我有两个字符串，比如 str1 和 str2。我需要将第一个转换为第二个，同时进行最少的编辑。这就是所谓的编辑距离。假设我们需要将Sunday转换为Saturday。第一个字母相同，后三个字母也相同，所以归结为将un转换为atur。这可以通过 3 个步骤完成 - 将 'n' 替换为 'r'、插入 't'、插入 'a'。这给出了编辑距离为 3。以下是找出编辑距离的程序 -

// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
#include<bits/stdc++.h>
using namespace std;

// Utility function to find minimum of three numbers
int min(int x, int y, int z) 
{
    return min(min(x, y), z);
}

int editDistDP(string str1, string str2, int m, int n)
{
    // Create a table to store results of subproblems
    int dp[m+1][n+1];

    // Fill d[][] in bottom up manner
    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            // If first string is empty, only option is to
            // isnert all characters of second string
            if (i==0)
                dp[i][j] = j;  // Min. operations = j

            // If second string is empty, only option is to
            // remove all characters of second string
            else if (j==0)
                dp[i][j] = i; // Min. operations = i

            // If last characters are same, ignore last char
            // and recur for remaining string
            else if (str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1];

            // If last character are different, consider all
            // possibilities and find minimum
            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];
}

// Driver program
int main()
{
    // your code goes here
    string str1 = "sunday";
    string str2 = "saturday";

    cout << editDistDP(str1, str2, str1.length(), str2.length());

    return 0;
}

虽然这个 returns 是正确的结果，但我还需要输出准确的转换步骤，例如

周日 -> 周六 -> 周六 -> 周六。

如何进行第二步？

Answer 1

创建 dp table 后，您可以按照与创建 [=22] 相同的方式从 (m, n) 返回到 (0, 0) =].

这是打印修改的解决方案，但您也可以 return 修改向量。

int editDistDP(string str1, string str2)
{
    int m = str1.length();
    int n = str2.length();
    int dp[m + 1][n + 1];
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {            
                dp[i][j] = 1 + min3(dp[i][j - 1],
                                    dp[i - 1][j],
                                    dp[i - 1][j - 1]);
            }
        }
    }

    i = m; j = n;

    while (i && j) {
        if (i == 0) {
            cout << "insert " << str2[j - 1] << endl;
            j--;
        } else if (j == 0) {
            cout << "remove " << str1[i - 1] << endl;
            i--;
        } else if (str1[i - 1] == str2[j - 1]) {
            i--; j--;
        } else {        
            int k = imin3(dp[i][j - 1],
                          dp[i - 1][j],
                          dp[i - 1][j - 1]);

            if (k == 2) {
                cout << "replace " << str1[i - 1] 
                     << " with " << str2[j - 1] << endl;
                i--; j--;
            } else if  (k == 1) {
                cout << "remove " << str1[i - 1] << endl;
                i--;

            } else {
                cout << "insert " << str2[j - 1] << endl;
                j--;
            }
        }
    }

    return dp[m][n];
}

这里，imin3是一个函数，return是列表中最小元素的索引0、1或2。

以最短路径将一个字符串转换为另一个字符串

Convert a string to another string in the shortest path

algorithm

edit-distance

dynamic-programming