最短パスの文字列を別の文字列に変換する

Question

私は2つの文字列、たとえばstr1とstr2を持っています。最初のものを2番目のものに変換する必要がありますが、編集回数は最小限に抑えます。これは編集距離と呼ばれます。 SundayをSaturdayに変換する必要があるとします。最初の文字は同じで、最後の3文字も同じであるため、unからaturに変換されます。これは、3つのステップで行うことができます - 'n'を 'r'で置き換え、 't'を挿入し、 'a'を挿入します。すなわち、

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

これが正しい結果を返しますが、私はまた、出力への変換の正確な手順を必要とする

のようなものを - それは編集距離を見つけるためのプログラムである後3として編集距離を与えます

日曜日 - >日曜日 - >曜日 - >土曜日。

2番目の手順はどのように行いますか？

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を返す関数です。