【C++】文字列を括弧で囲んだ部分文字列の全パターンを出力する方法

この問題では、与えられた文字列を部分文字列に分割し、それぞれを括弧で囲んで出力する必要があります。

まず、具体例を見ながら問題を理解しましょう。

入力 : wxyz
出力 :
    (w) (x) (y) (z)
    (w) (x) (yz)
    (w) (xy) (z)
    (w) (xyz)
    (wx) (y) (z)
    (wx) (yz)
    (wxy) (z)
    (wxyz)

解説 − 文字列を考えられるすべての部分文字列の組み合わせに分割し、それぞれの部分文字列を括弧で囲んで表示します。長さ n の文字列の場合、分割パターンは 2^n-1 通り存在します。

問題の内容が理解できたところで、解決策を作成していきましょう。

ここでは再帰を使ってこの問題を解きます。再帰関数には2つのパラメータを渡します。1つは現在処理中の位置を示すインデックス、もう1つはこれまでに構築した出力文字列です。未処理の部分文字列は再帰の各呼び出しで少しずつ処理され、すべての分割パターンが生成されていきます。

実装例

この問題を解くプログラムは以下のとおりです。

#include <iostream>
using namespace std;

void substring(string str, int index, string out){
    // 文字列の終端に到達したら、完成したパターンを出力
    if (index == str.length()){
        cout << out << endl;
        return;
    }
    // index 以降の各位置で文字列を分割しながら再帰呼び出し
    for (int i = index; i < str.length(); i++)
        substring(str, i + 1, out + "(" + str.substr(index, i + 1 - index) + ")");
}

int main(){
    string str = "wxyz";
    cout << "部分文字列のパターン :" << endl;
    substring(str, 0, "");
    return 0;
}

出力

部分文字列のパターン :
(w)(x)(y)(z)
(w)(x)(yz)
(w)(xy)(z)
(w)(xyz)
(wx)(y)(z)
(wx)(yz)
(wxy)(z)
(wxyz)

アルゴリズムのポイント

この再帰の仕組みを簡単に整理すると、次のようになります。

• 関数は現在のインデックスから文字列の終わりまでの各位置 i について、index から i までの部分文字列を切り出し、括弧で囲んで出力文字列に追加します。
• その後、インデックスを i + 1 に進めて再帰呼び出しを行うことで、残りの文字列に対するすべての分割パターンを探索します。
• インデックスが文字列の長さに達した時点で、1つの完全なパターンが完成したことになるため、それを出力して再帰を終了します。

計算量は、長さ n の文字列に対して 2^n-1 通りのパターンが生成されるため、時間計算量は O(2ⁿ × n) となります。文字列が長くなるとパターン数が爆発的に増えるため、短い文字列向けのアルゴリズムである点に注意してください。