C++で一方の文字列を別の文字列に変換するすべての方法を出力する

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

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

• 挿入（Insert）
• 削除（Remove）
• 置換（Replace）

具体例を使って問題を理解しましょう。

入力：str1 = "kfeod"、str2 = "kfcadq"

出力

Way1:
d の後に q を挿入。
c を e に置換。
o を 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つの方法を出力することができます。すべての方法を出力するのはやや複雑で、文字列のベクトル（vector of strings）のような高度なデータ構造を使用する必要があります。これについては後ほど詳しく学びます。

アプローチの動作を示すプログラム

例

#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