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