数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中回文排列 II
假设我们有一个字符串 s，我们需要找到它所有的回文排列，并且没有重复。如果没有回文排列，则返回空字符串。
因此，如果输入像“aabb”，则输出将是 [“abba”, “baab”]。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 ret
定义一个函数 solve()，它将接收 s、sz、一个无序映射 m 和 idx，并将其初始化为 0，
如果 sz 等于 0，则：
将 s 插入 ret 的末尾
返回
evenFound := false
定义一个集合 visited
对于 m 的每个键值对 it，执行以下操作：
如果 it 的值为零，则：
（将其增加 1）
忽略以下部分，跳过到下一个迭代
否则，当 it 的值等于 1 时，则：
oddChar := it 的键
否则
如果 it 的键未在 visited 中，则
忽略以下部分，跳过到下一个迭代
s[idx] := it 的键
s[字符串 s 的大小 - 1 - idx] = it 的键
evenFound := true
m[it 的键] := m[it 的键] - 2
solve(s, sz - 2, m, idx + 1)
m[it 的键] := m[it 的键] + 2
将 it 的键插入 visited
（将其增加 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 中的每个键值对，执行以下操作：
当 it 的值为奇数时，将 oddCount 增加
（将其增加 1）
如果 oddCnt > 1，则：
返回 ret
solve(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, ]
177 次浏览
