C++で2つの文字列から生成できるすべてのインターリービング文字列を出力する方法

問題の概要

この問題では、2つの文字列 str1 と str2 が与えられ、これらの文字列から作成できるすべてのインターリービング文字列（交互結合文字列）を出力することが求められます。

インターリービング文字列とは？

インターリービング文字列とは、与えられた2つの文字列の文字を交互に組み合わせて作られる文字列のことです。重要なポイントとして、各文字列内の文字の相対的な順序は維持される必要があります。

具体例で問題を確認してみましょう。

入力: str1 = "XY"、str2 = "NS"
出力: XYNS, XNYS, XNSY, NXYS, NXSY, NSXY

上記の出力結果を見ると、どの文字列でも「X」は「Y」より先に現れ、「N」は「S」より先に現れています。つまり、元の文字列の順序が保たれたまま、2つの文字列の文字があらゆるパターンで混ざり合っています。

解決のアプローチ

この問題を解くためには、両方の文字列のすべての文字を考慮する必要があります。str1 の長さを m、str2 の長さを n とすると、これらの文字列から生成できるインターリービング文字列は全部で (m+n)! / (m! × n!) 通り存在します。

すべてのインターリービング文字列を出力する基本的な考え方は以下の通りです。

• 現在の位置に str1 の先頭文字を置くか、str2 の先頭文字を置くかの2択を毎回選ぶ
• 文字を1つ配置したら、残りの文字列に対して再帰的に同じ処理を呼び出す
• 両方の文字列が空になった時点で、完成した文字列を出力する

このように、文字を固定しながら再帰呼び出しを繰り返すことで、すべての組み合わせを網羅的に生成できます。

C++での実装例

上記のロジックを実装したコードがこちらです。

#include <iostream>
#include <string.h>
using namespace std;

void printStrings(char *str1, char *str2, char *iStr, int m, int n, int i) {
    // 両方の文字列を使い切ったら結果を出力
    if (m == 0 && n == 0)
        cout << iStr << endl;
    // str1 に残り文字がある場合はその先頭文字を採用
    if (m != 0) {
        iStr[i] = str1[0];
        printStrings(str1 + 1, str2, iStr, m - 1, n, i + 1);
    }
    // str2 に残り文字がある場合はその先頭文字を採用
    if (n != 0) {
        iStr[i] = str2[0];
        printStrings(str1, str2 + 1, iStr, m, n - 1, i + 1);
    }
}

void generateInterleavingString(char *str1, char *str2, int m, int n) {
    // 結果を格納するバッファを確保（終端文字分も含む）
    char *iStr = new char[(m + n + 1) * sizeof(char)];
    iStr[m + n] = '\0';
    printStrings(str1, str2, iStr, m, n, 0);
}

int main() {
    char str1[] = "XY";
    char str2[] = "NS";
    cout << "All interleaving string are :\n";
    generateInterleavingString(str1, str2, strlen(str1), strlen(str2));
    return 0;
}

実行結果

All interleaving string is −
XYNS
XNYS
XNSY
NXYS
NXSY
NSXY

処理の流れのポイント

• 終了条件： m == 0 かつ n == 0 のとき、つまり両方の文字列の文字をすべて使い切った時点で、構築済みの文字列 iStr を出力します。
• 再帰ステップ： 各再帰呼び出しでは、str1 または str2 のどちらか一方から先頭の1文字を取り出して結果バッファに配置し、対応するポインタを1つ進めて再帰します。
• 計算量： 結果の総数は二項係数 C(m+n, m) に等しく、各文字列の長さが長くなると組み合わせの数は急激に増加するため、長い文字列に対しては注意が必要です。

この手法はバックトラッキングの一種であり、文字列の組み合わせを扱う多くの応用問題（文字列マッチングの検証など）にも応用できます。