問題定義

特定の入力文字列を受け取り、それを複数の部分文字列に分割する際、各部分文字列が必ずパリンドローム（読み返しても同一になる列）となるようなすべての組み合わせを求めるタスクです。

探索アプローチの設計

この種の分割問題は、標準的なループ制御のみで実装しようとすると境界条件や重複チェックが複雑化しやすくなります。代わりに、選択枝を並木道のように分岐させる「バックトラッキング（後退法）」を用いるのが一般的です。

文字列の区切り位置を決定する過程は、本質的に部分集合を作成する組み合わせ問題と構造が類似しています。ある位置で文字を区切った場合、残りの文字列に対して再度同様の選択を行うため、これは明確な木構造グラフとしてモデル化できます。深さ優先探索で縦方向に進み、Forループで横方向の選択肢を試していくイメージで実装します。

再帰フレームワークの構築

探索ロジックを実装するには、以下の三要素を整備します。

• 引数の管理: 現在までに確定した分割リスト、最終的な解答群、そして次に着目するインデックスが必要です。既に処理済みの文字を重複して切断しないよう、開始位置を示すパラメータを保持します。
• 停止条件: 探索対象のインデックスが入力長を超えた時点で、有効な分割パターンが一つ見つかったことになります。このタイミングで現在の状態を記録し、呼び出し元へ戻ります。
• 単一層の探索処理: 開始位置から末尾まで範囲を広げながら、取り出した区間がパリンドロームであるか判定します。合致すればその区間を現在の候補に加えて再帰呼び出しを行い、処理が完了したらそれを外す（バックトラック）ことで次の区間の試行に移ります。

基礎実装：直接判定版

各カット位置で二点間比較（ポインター操作）を行い回文かどうかをチェックする方法です。

class PalindromeDivider {
private:
    std::vector<std::vector<std::string>> solutions;
    std::vector<std::string> currentSplit;

    void explore(const std::string& text, int cursor) {
        // 終了基準：カーソルが文字列末尾を過ぎた
        if (cursor >= text.length()) {
            solutions.push_back(currentSplit);
            return;
        }

        // 開始位置から終端までスライスを広げる
        for (int end = cursor; end < text.length(); ++end) {
            // カット幅が正常かつパリンドロームなら
            if (checkPalindrome(text, cursor, end)) {
                currentSplit.push_back(text.substr(cursor, end - cursor + 1));
                // 次の切断位置へ再帰
                explore(text, end + 1);
                // 選択解除（バックトラック）
                currentSplit.pop_back();
            }
        }
    }

    bool checkPalindrome(const std::string& s, int left, int right) const {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }

public:
    std::vector<std::vector<std::string>> findAllPartitions(std::string input) {
        solutions.clear();
        currentSplit.clear();
        explore(input, 0);
        return solutions;
    }
};

計算量評価

上記の素朴な実装では、最悪ケースにおいて時間計算量が $O(n \times 2^n)$、再帰スタックと配列保持のために空間計算量が $O(n^2)$ 程度になります。$n$ は文字列長です。

最適化戦略：前計算テーブルの活用

直接的な判定関数を毎度実行すると、重複する部分文字列の評価コストが累積してしまいます。例えば「bcb」が回文でないことが分かれば、「abcb...」も確実に回文ではありません。この性質を活用し、事前に動的計画法（DP）によって任意の区間 $[i, j]$ の回文判定結果をテーブルに格納しておくと、探索時のオーバーヘッドを大きく削減できます。

DP表 $memo[i][j]$ は、$s[i] == s[j]$ であり、かつ内部 $s[i+1 \dots j-1]$ が回文である場合に成立します。境界条件として長さ1または2の文字列は単純な一致判定だけで済みます。

高速化実装例

class FastPalindromePartitioner {
private:
    std::vector<std::vector<std::string>> validCombos;
    std::vector<std::string> activePath;
    std::vector<std::vector<bool>> dpTable;

    void buildMemo(const std::string& str) {
        int n = str.length();
        dpTable.assign(n, std::vector<bool>(n, false));

        // 右端から左方向へ逆算することで依存関係を解決
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j) {
                    dpTable[i][j] = true;
                } else if (j == i + 1) {
                    dpTable[i][j] = (str[i] == str[j]);
                } else {
                    dpTable[i][j] = (str[i] == str[j] && dpTable[i + 1][j - 1]);
                }
            }
        }
    }

    void traverse(const std::string& str, int startIdx) {
        if (startIdx == str.length()) {
            validCombos.push_back(activePath);
            return;
        }

        for (int cutPoint = startIdx; cutPoint < str.length(); ++cutPoint) {
            if (dpTable[startIdx][cutPoint]) {
                activePath.push_back(str.substr(startIdx, cutPoint - startIdx + 1));
                traverse(str, cutPoint + 1);
                activePath.pop_back();
            }
        }
    }

public:
    std::vector<std::vector<std::string>> solve(std::string target) {
        validCombos.clear();
        activePath.clear();
        
        if (!target.empty()) {
            buildMemo(target);
            traverse(target, 0);
        }
        return validCombos;
    }
};

このようにメモ化を行えば、探索中の回文判定が定数時間 $O(1)$ に抑えられ、全体の実行効率を向上させられます。