C++で文字列の文字間にスペースを挿入して作成できる全パターンを出力する方法

この問題では、1つの文字列が与えられ、その文字列の各文字の間にスペースを挿入することで作成できる、すべてのパターンの文字列を出力することが求められます。

具体例を使って、このトピックをより深く理解してみましょう。

入力：string = 'XYZ'
出力：XYZ, XY Z, X YZ, X Y Z

解決のアプローチ

この問題を解くためには、文字列内にスペースを挿入できるすべての可能な組み合わせを見つける必要があります。そのために再帰（リカージョン）を活用します。

基本的な考え方は以下の通りです。

• 各文字について、「スペースを入れない」場合と「スペースを入れる」場合の2つの選択肢があります。
• 再帰呼び出しを通じて、両方の選択肢を順番に試していきます。
• すべての文字を処理し終えた時点で、バッファに格納された文字列を出力します。

それでは、実際のコードを見てみましょう。

サンプルコード

#include <iostream>
#include <cstring>
using namespace std;

void printPattern(char str[], char buff[], int i, int j, int n){
    // すべての文字を処理したら、バッファを終端して出力
    if (i == n){
        buff[j] = '\0';
        cout << buff << endl;
        return;
    }
    // スペースを入れないケース
    buff[j] = str[i];
    printPattern(str, buff, i+1, j+1, n);
    // スペースを入れるケース
    buff[j] = ' ';
    buff[j+1] = str[i];
    printPattern(str, buff, i+1, j+2, n);
}

int main() {
    char *str = "XYZ";
    int n = strlen(str);
    char buf[2*n];
    buf[0] = str[0];
    cout<<"スペース挿入で生成される文字列パターン：\n";
    printPattern(str, buf, 1, 1, n);
    return 0;
}

実行結果

スペース挿入で生成される文字列パターン：
XYZ
XY Z
X YZ
X Y Z

コードの解説

このプログラムの動作を詳しく見ていきましょう。

• printPattern関数：引数として元の文字列str、結果を格納するバッファbuff、現在処理中の文字位置i、バッファへの書き込み位置j、文字列の長さnを受け取ります。
• 終了条件：iがnに達したとき、つまりすべての文字を処理し終えたときに、バッファにNULL終端文字を追加して文字列を出力します。
• 再帰ステップ：まず現在の文字をそのままコピーして次へ進むパターンと、スペースを1つ挟んでから文字をコピーするパターンの2つの再帰呼び出しを行います。

なお、長さnの文字列に対して、スペースを挿入できる箇所はn-1箇所あるため、生成されるパターンの総数は 2^(n-1) 個になります。上記の例では「XYZ」の3文字なので、2^2 = 4通りのパターンが出力されていることが確認できます。

まとめ

このように、再帰を用いることで、文字列の各文字間にスペースを挿入するかどうかの選択を組み合わせ的に展開し、すべての可能なパターンを効率的に生成・出力することができます。同様の手法は、部分集合の列挙やビット全探索の考え方にも通じるため、アルゴリズム学習においても非常に有用なテクニックです。