ধরুন আমরা একটি স্ট্রিং s এবং স্ট্রিং জোড়ায় সূচকের জোড়ার একটি অ্যারে দিয়েছি যেখানে জোড়া[i] =[a, b] স্ট্রিংয়ের 2টি সূচক (0-সূচীযুক্ত) নির্দেশ করে। আমরা যতবার চাই ততবার প্রদত্ত জোড়ার যেকোন জোড়া সূচকে অক্ষরগুলিকে অদলবদল করতে পারি। আমাদের আভিধানিকভাবে সবচেয়ে ছোট স্ট্রিংটি খুঁজে বের করতে হবে যেটি s সোয়াপ ব্যবহার করার পরে পরিবর্তন করা যেতে পারে। সুতরাং ইনপুট যদি s =“dcab” এবং জোড়া =[[0,3], [1,2]] এর মত হয়, তাহলে আউটপুট হবে “bacd”। বিনিময় করুন s[0] এবং s[3], s ="bcad", তারপর বিনিময় করুন s[1] এবং s[2], s ="bacd"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=অ্যারের আকার, অভিভাবক :=n আকারের একটি অ্যারে তৈরি করুন এবং এটি -1 দিয়ে পূরণ করুন
-
ret of size n নামে একটি স্ট্রিং তৈরি করুন এবং এটি *
দিয়ে পূরণ করুন -
আমার জন্য 0 থেকে জোড়ার আকারের মধ্যে
-
u :=জোড়া[i, 0] এবং v :=জোড়া[i, 1]
-
যদি u-এর অভিভাবক v-এর পিতা-মাতার সমান হয়, তাহলে পরবর্তী পুনরাবৃত্তিতে চলে যান
-
পিতামাতা [u এর পিতামাতা] :=v
এর পিতামাতা
-
-
n
আকারের একটি অ্যারে arr1 সংজ্ঞায়িত করুন -
0 থেকে n – 1 রেঞ্জের i জন্য:arr[i-এর পিতামাতা]
-এ s[i] ঢোকান -
0 থেকে n – 1 রেঞ্জের i এর জন্য:ডান থেকে মান পড়ে arr[i] সাজান
-
0 থেকে n – 1 −
রেঞ্জের i জন্য-
ret[i] :=arr1[i-এর পিতা]
এর শেষ এন্ট্রি -
arr1[i-এর পিতা]
থেকে শেষ নোড মুছুন
-
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
class Solution {
public:
vector <int> parent;
int getParent(int x){
if(parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
parent = vector <int>(n, -1);
string ret(n, '*');
for(int i = 0; i < pairs.size(); i++){
int u = pairs[i][0];
int v = pairs[i][1];
if(getParent(u) == getParent(v)) continue;
parent[getParent(u)] = getParent(v);
}
vector < char > arr1[n];
for(int i = 0; i < n; i++){
arr1[getParent(i)].push_back(s[i]);
}
for(int i = 0; i < n; i++){
sort(arr1[i].rbegin(), arr1[i].rend());
}
for(int i = 0; i < n; i++){
ret[i] = arr1[getParent(i)].back();
arr1[getParent(i)].pop_back();
}
return ret;
}
}; ইনপুট
"dcab" [[0,3],[1,2]]
আউটপুট
"bacd"
