सी++ में पैलिंड्रोम क्रमचय II

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

इसलिए, यदि इनपुट "आब" जैसा है, तो आउटपुट ["अब्बा", "बाब"]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सरणी रिट परिभाषित करें

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह s, sz, एक अनियंत्रित मानचित्र m लेगा, idx इसे 0 से प्रारंभ करेगा,

• यदि sz 0 के समान है, तो -

  • रिट के अंत में s डालें

  • वापसी

• ईवनफाउंड:=झूठा

• देखे गए एक सेट को परिभाषित करें

• m के प्रत्येक कुंजी-मान युग्म के लिए, −

  . करें

  • यदि इसका मान शून्य है, तो -

    • (इसे 1 से बढ़ाएं)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • अन्यथा जब इसका मान 1 के समान हो, तो -

    • विषमचर:=इसकी कुंजी

  • अन्यथा

    • अगर इसकी चाबी नहीं देखी जाती है, तो

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • s[idx] :=इसकी कुंजी

    • s [s का आकार - 1 - idx] =इसकी कुंजी

    • ईवनफाउंड :=सच

    • एम [इसकी कुंजी]:=एम [इसकी कुंजी] - 2

    • हल करें(s, sz - 2, m, idx + 1)

    • एम [इसकी कुंजी]:=एम [इसकी कुंजी] + 2

    • विज़िट में इसकी कुंजी डालें

  • (इसे 1 से बढ़ाएं)

• अगर भी गलत पाया गया, तो -

  • s[idx] :=oddChar

  • हल करें(s, sz-1, m, idx + 1)

• मुख्य विधि से निम्न कार्य करें -

• एक मानचित्र को परिभाषित करें

• n :=s का आकार

• अस्थायी:=रिक्त स्ट्रिंग

• इनिशियलाइज़ i:=0 के लिए, जब i

  • (cnt[s[i]] 1 से बढ़ाएं)

  • अस्थायी:=अस्थायी "*"

• ऑडसीएनटी:=0

• cnt में प्रत्येक की-वैल्यू पेयर के लिए, −

  . करें

  • विषम गणना बढ़ाएं जब इसका मान विषम हो

  • (इसे 1 से बढ़ाएं)

• अगर विषम> 1, तो -

  • वापसी रिट

• हल करें (अस्थायी, एन, सीएनटी)

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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, ]