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