資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
