C ++中的回文排列II

假设我们有一个字符串s，我们必须找到它的所有回文排列，就不会重复。如果没有回文排列，则只需返回空字符串。

因此，如果输入类似于“ aabb”，则输出将为[“ abba”，“ baab”]

为了解决这个问题，我们将遵循以下步骤-

• 定义数组ret

• 定义一个函数solve()，它将使用s，sz，一个无序映射m，idx将其初始化为0，

• 如果sz与0相同，则-

• 在ret的末尾插入s

• 返回

• evenFound：=假

• 定义一组参观

• 对于m的每个键值对，执行-

• 如果没有访问它的键，则

• s [idx]：=它的键

• s [s的大小-1-idx] =它的键

• evenFound：=真

• m [它的键]：= m [它的键]-2

• 解决（s，sz-2，m，idx +1）

• m [它的键]：= m [它的键] + 2

• 将其键插入访问

• 忽略以下部分，跳至下一个迭代

• 奇数：=它的关键

• （增加1）

• 忽略以下部分，跳至下一个迭代

• 如果它的值为零，则-

• 否则，当它的值等于1时，则-

• 除此以外

• （增加1）

• 如果evenFound为false，则-

• s [idx]：=奇数字符

• 解决（s，sz-1，m，idx +1）

• 从主要方法中执行以下操作-

• 定义一个映射

• n：= s的大小

• temp：=空字符串

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• （将cnt [s [i]]增加1）

• temp：= temp并置“ *”

• 奇数：= 0

• 对于cnt中的每个键值对，请执行以下操作-

• 当其值为奇数时增加奇数

• （增加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, ]