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

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;
}

虽然这会返回正确的结果，但我还需要输出准确的转换步骤，例如

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

第二步我该怎么做？

Answer 1

一旦你创建了你的 dp 表，你就可以从 (m, n) 回到 (0, 0)与创建表格的方式相同。

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

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 是一个函数，返回列表中最小元素的索引 0、1 或 2。