C++で文字列の回文順列をすべて生成する方法（Palindrome Permutation II）

文字列 s が与えられたとき、その文字を並べ替えて作ることができる「回文（パリンドローム）」となる順列をすべて求める問題です。結果に重複は含めず、回文順列がひとつも存在しない場合は空の結果を返します。

たとえば、入力が "aabb" の場合、出力は ["abba", "baab"] となります。

解法のアプローチ

この問題はバックトラッキング（試行と巻き戻し）を使うことで効率的に解けます。まず各文字の出現回数を数え、奇数回現れる文字が2種類以上ある場合は回文を構成できないため、その時点で空の結果を返します。回文にできる場合は、左右対称の位置へ同じ文字をペアで配置しながら再帰的に文字列を組み立てていきます。

具体的な手順は以下の通りです。

• 結果を格納する配列 ret を用意する
• 関数 solve() を定義する。引数は文字列 s、残りのサイズ sz、文字数を管理するマップ m、現在のインデックス idx（初期値は0）
• sz が 0 になった場合、s を ret の末尾に追加して処理を終える（回文が完成）
• フラグ evenFound を false で初期化する
• 同一呼び出し内で使用済みの文字を記録するセット visited を用意する
• m 内の各キーと値 it に対して次を繰り返す
  • 値が 0 の場合は何もせず次へ進む
  • 値が 1 の場合は、そのキーを oddChar として記録する（回文の中央に置く候補）
  • 値が 2 以上の場合は次のように処理する
    • キーがすでに visited に含まれていればスキップする
    • s[idx] と s[s.size() - 1 - idx] にそのキーの文字を代入する
    • evenFound を true にする
    • m[キー] の値を 2 減らす
    • solve(s, sz - 2, m, idx + 1) を再帰呼び出しする
    • m[キー] の値を 2 増やして状態を元に戻す（バックトラック）
    • キーを visited に追加する
• ループ終了後も evenFound が false のままの場合（文字列長が奇数のケース）、s[idx] に oddChar を代入し、solve(s, sz - 1, m, idx + 1) を呼び出して中央の文字を確定させる

メインのメソッドでは以下を実行します。

• 文字の出現回数を数えるためのマップ cnt を定義する
• n を文字列 s のサイズとする
• temp を空文字列として初期化し、各文字について cnt のカウントを増やしながら、temp にはプレースホルダ "*" を1文字ずつ追加する
• oddCnt を 0 で初期化し、cnt の各値が奇数であれば oddCnt をインクリメントする
• oddCnt が 1 より大きければ、回文が構成できないため ret を返す
• solve(temp, n, cnt) を呼び出す
• ret を返す

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<string> ret;
   void solve(string s, int sz, unordered_map<char,int>& m, int idx = 0){
      if (sz == 0) {
         ret.push_back(s);
         return;
      }
      bool evenFound = false;
      char oddChar;
      unordered_map<char, int>::iterator it = m.begin();
      set<char> visited;
      while (it != m.end()) {
         if (!it->second) {
            it++;
            continue;
         }
         else if (it->second == 1) {
            oddChar = it->first;
         }
         else {
            if (visited.count(it->first))
               continue;
            s[idx] = it->first;
            s[s.size() - 1 - idx] = it->first;
            evenFound = true;
            m[it->first] -= 2;
            solve(s, sz - 2, m, idx + 1);
            m[it->first] += 2;
            visited.insert(it->first);
         }
         it++;
      }
      if (!evenFound) {
         s[idx] = oddChar;
         solve(s, sz - 1, m, idx + 1);
      }
   }
   vector<string> generatePalindromes(string s){
      unordered_map<char,int> cnt;
      int n = s.size();
      string temp = "";
      for (int i = 0; i < n; i++) {
         cnt[s[i]]++;
         temp += "*";
      }
      int oddCnt = 0;
      unordered_map<char, int>::iterator it = cnt.begin();
      while (it != cnt.end()) {
         oddCnt += (it->second & 1);
         it++;
      }
      if (oddCnt > 1)
         return ret;
      solve(temp, n, cnt);
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.generatePalindromes("aabb"));
}

入力

"aabb"

出力

[baab, abba]

ポイントまとめ

この手法では、文字をペアごとに左右対称の位置へ配置していくため、探索空間を大幅に絞り込むことができます。すべての順列を生成してから回文かどうか判定する方式（計算量 O(n!)）と比べ、回文になり得ない分岐を早い段階で切り捨てられる点が大きな利点です。また、事前に奇数回出現する文字の数をチェックすることで、解が存在しないケースを即座に見抜けるのも実装上の重要なポイントといえます。