Convert a string to another string in the shortest path

Question

I have two strings, say str1 and str2. I need to convert the first one to the second one while making the least number of edits. This is what is called as Edit Distance. Suppose we need to convert Sunday to Saturday. The first letter is the same, and the last three are the same as well, so it boils down to converting un to atur. This can be done in 3 steps - Replace 'n' with 'r', insert 't', insert 'a'. That gives the edit distance as 3. Following is the program to find out the edit distance -

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

While this returns the correct result, I also need to output the exact steps of conversion, i.e. something like

Sunday -> Surday -> Sturday -> Saturday.

How do I do the second step?

This may help, you basically want to find the smallest diff in 2 strings http://stackoverflow.com/questions/1510225/how-do-document-diff-algorithms-work — Abhishek Sinha, Apr 15 '16 at 12:23

score 3 · Accepted Answer · answered Apr 15 '16 at 13:18

Once you have created your dp table, you can work your way back rom (m, n) to (0, 0) in the same way as you created the table.

Here's a solution that prints the modifications, but you could also return a vector of modifications.

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

Here, imin3 is a function that returns the index 0, 1 or 2 of the minimum element in the list.

Convert a string to another string in the shortest path

1 Answers1