ধরুন আমাদের কাছে 'D' এবং 'I' অক্ষর সমন্বিত একটি গোপন স্বাক্ষর রয়েছে। 'D' দুটি সংখ্যার মধ্যে ক্রমবর্ধমান সম্পর্ক নির্দেশ করে, 'I' দুটি সংখ্যার মধ্যে ক্রমবর্ধমান সম্পর্ক নির্দেশ করে। এবং গোপন স্বাক্ষরটি একটি বিশেষ পূর্ণসংখ্যা অ্যারে দ্বারা তৈরি করা হয়েছিল, যা অনন্যভাবে 1 থেকে n পর্যন্ত সমস্ত ভিন্ন সংখ্যা ধারণ করে৷
উদাহরণস্বরূপ, গোপন স্বাক্ষর "DI" [2,1,3] বা [3,1,2] এর মতো অ্যারে থেকে তৈরি করা যেতে পারে, তবে [3,2,4] বা [2, এর মতো অ্যারে ব্যবহার করে তৈরি করা যাবে না। 1,3,4], যা উভয়ই অবৈধ নির্মাণ বিশেষ স্ট্রিং যা "DI" গোপন স্বাক্ষর উপস্থাপন করতে পারে না।
এখন আমাদের [1, 2, ... n] এর আভিধানিকভাবে ক্ষুদ্রতম স্থানান্তর খুঁজে বের করতে হবে যা ইনপুটে প্রদত্ত গোপন স্বাক্ষরকে নির্দেশ করতে পারে।
সুতরাং, যদি ইনপুটটি "DI" এর মতো হয়, তবে আউটপুট হবে [2,1,3], যেমনটি আমরা জানি [3,1,2] এছাড়াও গোপন স্বাক্ষর "DI" তৈরি করতে পারে, কিন্তু যেহেতু আমরা খুঁজে পেতে চাই যেটির মধ্যে সবচেয়ে ছোট লেক্সিকোগ্রাফিক্যাল পারমুটেশন আছে, আমাদের আউটপুট করতে হবে [2,1,3]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
cnt :=2
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=1, যখন i <=s এর আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
-
যদি s[i - 1] 'D' এর মত হয়, তাহলে −
-
আমাকে st
-এ ঢোকান
-
-
অন্যথায়
-
ret এর শেষে i ঢোকান
-
যখন (st খালি নয়), −
করুন-
ret এর শেষে st-এর শীর্ষ উপাদান সন্নিবেশ করুন
-
st
থেকে উপাদান মুছুন
-
-
-
-
st
-এ s-এর মাপ সন্নিবেশ করান -
যখন (st খালি নয়), −
করুন-
ret এর শেষে st-এর শীর্ষ উপাদান সন্নিবেশ করুন
-
st
থেকে উপাদান মুছুন
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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<int< findPermutation(string s) {
stack <int< st;
int cnt = 2;
vector <int< ret;
for(int i = 1; i <= s.size(); i++){
if(s[i - 1] == 'D'){
st.push(i);
}
else{
ret.push_back(i);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
}
}
st.push(s.size() + 1);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findPermutation("DIID"));
} ইনপুট
"DIID"
আউটপুট
[2, 1, 3, 5, 4, ]
