สมมติว่าเรามีสตริง s เราต้องหาการเรียงสับเปลี่ยนพาลินโดรมทั้งหมดของมัน จะไม่มีการซ้ำซ้อน หากไม่มีการเรียงสับเปลี่ยนพาลินโดรม ก็ให้คืนค่าสตริงว่าง
ดังนั้น หากอินพุตเป็นเหมือน "aabb" ผลลัพธ์จะเป็น ["abba", "baab"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดอาร์เรย์ ret
-
กำหนดฟังก์ชัน แก้ไข () ซึ่งจะใช้เวลา s, sz, หนึ่งแผนที่ที่ไม่เรียงลำดับ m, idx เริ่มต้นด้วย 0
-
ถ้า sz เท่ากับ 0 แล้ว −
-
ใส่ s ต่อท้าย ret
-
กลับ
-
-
evenFound :=เท็จ
-
กำหนดการเยี่ยมชมหนึ่งชุด
-
สำหรับคู่คีย์-ค่าแต่ละคู่เป็น m ให้ทำ -
-
ถ้าค่าของมันเป็นศูนย์ ดังนั้น −
-
(เพิ่มขึ้นอีก 1)
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
มิฉะนั้นเมื่อค่าเท่ากับ 1 แล้ว −
-
oddChar :=คีย์ของมัน
-
-
มิฉะนั้น
-
ถ้าคีย์ไม่เข้าก็
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
s[idx] :=คีย์ของมัน
-
s[ขนาดของ s - 1 - idx] =คีย์ของมัน
-
evenFound :=จริง
-
m[คีย์ของมัน] :=m[คีย์ของมัน] - 2
-
แก้(s, sz - 2, m, idx + 1)
-
m[คีย์ของมัน] :=m[คีย์ของมัน] + 2
-
ใส่คีย์ของมันลงในการเยี่ยมชม
-
-
(เพิ่มขึ้นอีก 1)
-
-
ถ้าพบเท็จแล้ว −
-
s[idx] :=oddChar
-
แก้(s, sz - 1, m, idx + 1)
-
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดหนึ่งแผนที่ cnt
-
n :=ขนาดของ s
-
temp :=สตริงว่าง
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
(เพิ่ม cnt[s[i]] ขึ้น 1)
-
temp :=temp concatenate " * "
-
-
oddCnt :=0
-
สำหรับคู่คีย์-ค่าแต่ละคู่เป็น cnt ให้ทำ -
-
เพิ่ม oddCount เมื่อค่าของมันเป็นเลขคี่
-
(เพิ่มขึ้นอีก 1)
-
-
ถ้า oddCnt> 1 แล้ว −
-
รีเทิร์น
-
-
แก้ (อุณหภูมิ n, cnt)
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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, ]
