Palindrome Permutation II - Sinh tất cả hoán vị palindrome

Cho chuỗi s, sinh tất cả hoán vị palindrome duy nhất. Nếu không có trả về rỗng.

Ví dụ: "aabb" → ["abba","baab"].

Giải thuật (Backtracking xây dựng nửa chuỗi)

Đếm tần suất ký tự. Nếu >1 ký tự lẻ → không có palindrome. Xây dựng nửa đầu: chọn cặp ký tự (tần suất ≥2) đặt đối xứng hai đầu. Ký tự lẻ (nếu có) đặt giữa. Dùng backtracking sinh tất cả.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    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;
        set<char> visited;

        for (auto it = m.begin(); it != m.end(); ++it) {
            if (it->second == 0) continue;
            else if (it->second == 1) oddChar = it->first;
            else {
                if (visited.count(it->first)) continue;
                s[idx] = s[s.size()-1-idx] = it->first;
                evenFound = true;
                it->second -= 2;
                solve(s, sz-2, m, idx+1);
                it->second += 2;
                visited.insert(it->first);
            }
        }
        if (!evenFound) {
            s[idx] = oddChar;
            solve(s, sz-1, m, idx+1);
        }
    }

    vector<string> generatePalindromes(string s) {
        unordered_map<char,int> cnt;
        string temp;
        for (char c : s) { cnt[c]++; temp += '*'; }
        int oddCnt = 0;
        for (auto& p : cnt) oddCnt += (p.second & 1);
        if (oddCnt > 1) return ret;
        solve(temp, s.size(), cnt);
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.generatePalindromes("aabb"));
    return 0;
}

Đầu vào

"aabb"

Đầu ra

[baab, abba, ]