C++ 中的回文排列 II
假设我们有一个字符串 s，我们需要找出它的所有回文排列，其中不包含重复。如果不存在回文排列，则返回空字符串。
因此，如果输入类似于"aabb"，则输出将为 ["abba"，"baab"]
为了解决这个问题，我们将遵循以下步骤 −
定义一个数组 ret
定义一个函数 resolve()，该函数接受 s、sz、一个无序映射 m 和 idx 作为参数，并将其初始化为 0
如果 sz 等于 0，则 −
在 ret 的末尾插入 s
返回
evenFound := false
定义一个已访问的集合
对 m 中的每个键值对 it 执行 −
如果 it 的值是 0，则执行 −
(将其加 1)
忽略以下部分，跳至下一次迭代
否则，当 it 的值等于 1 时，执行 −
oddChar := it 的 key
否则
如果 it 的 key 未被访问，则
忽略后续部分，跳至下一次迭代
s[idx] := 它的键
s[s 的大小 - 1 - idx] = 它的键
evenFound := true
m[它的键] := m[它的键] - 2
solve(s, sz - 2, m, idx + 1)
m[它的键] := m[它的键] + 2
将它的键插入到 visitor 中
(增加 1)
如果 evenFound 为 false，则−
s[idx] := oddChar
solve(s, sz - 1, m, idx + 1)
在主方法中执行以下操作 −
定义一个映射 cnt
n := s 的大小
temp := 空字符串
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
(将 cnt[s[i]] 增加 1)
temp := temp 连接 " * "
oddCnt := 0
对 cnt 中的每个键值对，执行 −
当 oddCount 为奇数时，增加 oddCount
(增加 1)
如果 oddCnt > 1，则 −
return ret
solve(temp, n, cnt)
return 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, ]
