ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের এটির সমস্ত প্যালিনড্রোমিক পারমুটেশন খুঁজে বের করতে হবে, কোন পুনরাবৃত্তি হবে না। যদি কোন প্যালিনড্রোমিক পারমুটেশন না থাকে, তাহলে খালি স্ট্রিং ফেরত দিন।
সুতরাং, ইনপুট যদি "aabb" এর মত হয়, তাহলে আউটপুট হবে ["abba", "baab"]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
একটি ফাংশন সমাধান সংজ্ঞায়িত করুন, এটি s, sz, একটি ক্রমবিহীন মানচিত্র m লাগবে, idx এটিকে 0 দিয়ে আরম্ভ করবে,
-
যদি sz 0 এর মত হয়, তাহলে −
-
ret এর শেষে s ঢোকান
-
ফেরত
-
-
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 হয়, তাহলে −
-
রিটার্ন রিটার্ন
-
-
সমাধান (temp, 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, ]
