C++ में पालिंड्रोम परम्यूटेशन II - सभी पालिंड्रोमिक परम्यूटेशन उत्पन्न करें

समस्या विवरण

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें इसके सभी पालिंड्रोमिक परम्यूटेशन ढूंढने हैं, कोई पुनरावृत्ति नहीं होगी। यदि कोई पालिंड्रोमिक परम्यूटेशन नहीं है, तो बस खाली स्ट्रिंग लौटाएं।

उदाहरण के लिए, यदि इनपुट "aabb" है, तो आउटपुट ["abba", "baab"] होगा।

समाधान दृष्टिकोण

बैकट्रैकिंग + वर्ण आवृत्ति गणना:

1. ret सरणी परिभाषित करें
2. solve() फ़ंक्शन परिभाषित करें जो s, sz, मैप m, idx (डिफ़ॉल्ट 0) लेता है:
   • यदि sz == 0, तो s को ret में जोड़ें और लौटें
   • evenFound := false
   • visited सेट परिभाषित करें
   • m के प्रत्येक कुंजी-मान जोड़े के लिए:
     • यदि मान 0 है, तो जारी रखें
     • यदि मान 1 है, तो oddChar := कुंजी
     • अन्यथा:
       • यदि कुंजी visited में है, तो जारी रखें
       • s[idx] := कुंजी, s[आकार-1-idx] := कुंजी
       • evenFound := true
       • m[कुंजी] -= 2
       • solve(s, sz-2, m, idx+1)
       • m[कुंजी] += 2
       • कुंजी को visited में डालें
   • यदि evenFound गलत है:
     • s[idx] := oddChar
     • solve(s, sz-1, m, idx+1)
3. मुख्य विधि से:
   • cnt मैप परिभाषित करें, n := s का आकार
   • temp := खाली स्ट्रिंग
   • प्रत्येक वर्ण के लिए cnt बढ़ाएं और temp में "*" जोड़ें
   • oddCnt := 0, विषम आवृत्ति वाले वर्ण गिनें
   • यदि oddCnt > 1, तो ret लौटाएं
   • solve(temp, n, cnt) कॉल करें
   • ret लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

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

इनपुट

"aabb"

आउटपुट

[baab, abba, ]