C++でのパリンドローム順列II

文字列sがあるとすると、そのすべての回文順列を見つける必要があり、繰り返しはありません。回文順列がない場合は、空の文字列を返すだけです。

したがって、入力が「aabb」のような場合、出力は["abba"、 "baab"]

これを解決するには、次の手順に従います-

• 配列retを定義する

• 関数solve（）を定義します。これには、s、sz、順序付けされていない1つのマップmが必要であり、idxは0で初期化します。

• szが0と同じ場合、-

  • retの最後にsを挿入します

  • 戻る

• evenFound：=false

• 訪問した1セットを定義する

• mのキーと値のペアごとに、次のようにします-

  • その値がゼロの場合、-

    • （1つ増やします）

    • 次の部分を無視し、次の反復にスキップします

  • それ以外の場合、その値が1と同じ場合、-

    • oddChar：=そのキー

  • それ以外の場合

    • キーにアクセスしていない場合は、

      • 次の部分を無視し、次の反復にスキップします

    • s [idx]：=そのキー

    • s[sのサイズ-1-idx]=そのキー

    • evenFound：=true

    • m [キーオブイット]：=m[キーオブイット]-2

    • 解決（s、sz-2、m、idx + 1）

    • m [キーオブイット]：=m[キーオブイット]+2

    • そのキーをvisitedに挿入します

  • （1つ増やします）

• 偽が見つかった場合でも、-

  • s [idx]：=oddChar

  • 解決（s、sz-1、m、idx + 1）

• メインの方法から、次のようにします-

• 1つのマップcntを定義する

• n：=sのサイズ

• temp：=空白の文字列

• 初期化i：=0の場合、i

  • （cnt [s [i]]を1増やします）

  • temp：=temp concatenate "*"

• oddCnt：=0

• cntのキーと値のペアごとに、次のようにします-

  • 値が奇数の場合はoddCountを増やします

  • （1つ増やします）

• oddCnt> 1の場合、-

  • retを返す

• 解決（temp、n、cnt）

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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, ]