C++で1つの文字列を別の文字列に変換するためのすべての可能な方法を印刷します

この問題では、2つの文字列str1とstr2が与えられます。 私たちのタスクは、ある文字列を別の文字列に変換するためのすべての可能な方法を印刷するプログラムを作成することです。

問題の説明： ここでは、str1をstr2に変換するために使用できるすべての方法を見つける必要があります。変換中に、3つの操作のいずれかを実行できます

• 挿入
• 削除
• 交換

問題を理解するために例を見てみましょう。

入力： str1 =“ kfeod” str2 =“ kfcadq”

出力

Way1:
Insert q, after d.
Replace c by e.
Replace o by a.

ソリューションアプローチ

最初に最小数の編集を見つけてから、DPマトリックスを作成します。次に、両方の文字列の要素に関連する文字が等しいかどうかを確認します。それ以外の場合は、最後の要素からコピーされるときに更新しないでください。

ここで、現在の文字DP [i] [j] =DP[i-1][j-1]。 str1の（i-1）番目の要素とstr2の（j-1）番目の要素が等しいかどうかを確認してから、DPを斜めにトラバースします。

ここで、str1の（i-1）番目の要素とstr2の（j-1）番目の要素が等しくない場合。 DP [i] [j]の値は（DP [i-1] [j-1]、DP[i][j-1]およびDP[i-1][j]からの最小値）+1です。

このメソッドは、ある文字列を別の文字列に変換する1つの方法を出力できます。すべての方法で印刷する方法は、文字列のベクトルのような高度なデータ構造を使用する少し注意が必要です。 後でそれについて学びます。

私たちのアプローチの仕組みを説明するプログラム

例

#include <iostream>
using namespace std;

int DP[100][100];

void findWays(string str1, string str2) {
   
   int len1 = str1.length();
   int len2 = str2.length();
   int i, j;
   DP[len1 + 1][len2 + 1];

   for (i = 0; i <= len1; i++)
      DP[i][0] = i;
   for (j = 0; j <= len2; j++)
      DP[0][j] = j;

   for (i = 1; i <= len1; i++) {
      for (j = 1; j <= len2; j++) {
         if (str1[i - 1] == str2[j - 1])
            DP[i][j] = DP[i - 1][j - 1];
         else
            DP[i][j] = (min(min(DP[i - 1][j - 1], DP[i - 1][j]), DP[i][j - 1])) + 1;
      }
   }
   while (len1 and len2) {

      if (str1[len1 - 1] == str2[len2 - 1]) {
         
         len1--;
         len2--;
      }
      else if (DP[len1][len2] == DP[len1-1][len2-1] + 1) {
         
         cout<<"\nModify '"<<str1[len1-1]<<"' to '"<<str2[len2-1];
         len1--;
         len2--;
      }
      else if (DP[len1][len2] == DP[len1-1][len2] + 1) {
         
         cout<<"\nRemove "<<str1[len1-1]<<"'";
         len1--;
      }
      else if (DP[len1][len2] == DP[len1][len2-1] + 1) {
         
         cout <<"\nInsert '"<<str2[len2-1]<<"'";
         len2--;
      }
   }
}

int main() {
   
   string str1 = "kfeodge";
   string str2 = "kfcadqpe";
   cout<<"Way to convert one string into another string is ";
   findWays(str1, str2);
   return 0;
}

出力

Way to convert one string into another string is
Modify 'g' to 'p
Insert 'q'
Modify 'o' to 'a
Modify 'e' to 'c