ধরুন আমাদের কাছে একটি স্ট্রিং আছে যা ছোট হাতের অক্ষর এবং বন্ধনী নিয়ে গঠিত। আমাদের প্রতিটি জোড়ার মিলিত বন্ধনীর স্ট্রিংগুলিকে বিপরীত করতে হবে, সবচেয়ে ভিতরের থেকে শুরু করে। এবং ফলাফলে কোন বন্ধনী থাকা উচিত নয়। সুতরাং ইনপুট যদি "(hel(lowo)rld)" এর মত হয়, তাহলে আউটপুট হবে "dlrlowoleh", তাই শুরু থেকে, এটি পরিবর্তন করা হয়েছে যেমন:"(hel(lowo)rld)" → "(helowolrld)" → "dlrowoleh"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=স্ট্রিংয়ের আকার, par নামক একটি অ্যারে তৈরি করুন যার দৈর্ঘ্য n, একটি স্ট্যাক st সংজ্ঞায়িত করুন
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি s[i] বন্ধনী খুলছে, তাহলে i ঢোকান st
-এ -
অন্যথায় যখন s[i] বন্ধনী বন্ধ করে, তখন j :=st.pop(), par[i] :=j এবং par[j] :=i
-
-
একটি খালি স্ট্রিং রিট সংজ্ঞায়িত করুন
-
i :=0, d :=1, i
-
যদি s[i] বন্ধনী খুলছে বা s[i] বন্ধনী বন্ধনী করছে, তাহলে i :=par[i], d :=-d অন্যথায় s[i] দ্বারা ret বাড়ান
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void out(vector <int>& v){
for(int i = 0; i < v.size(); i++){
cout << v[i] << " " ;
}
cout << endl;
}
string reverseParentheses(string s) {
int n = s.size();
vector <int> par(n);
stack <int> st;
for(int i = 0; i < n; i++){
if(s[i] == '('){
st.push(i);
}
else if(s[i] == ')'){
int j = st.top();
st.pop();
par[i] = j;
par[j] = i;
}
}
string ret = "";
for(int i = 0, d = 1; i < n; i += d){
if(s[i] == '(' || s[i] == ')'){
i = par[i];
d = -d;
}
else{
ret += s[i];
}
}
out(par);
return ret;
}
};
main(){
Solution ob;
cout << (ob.reverseParentheses("(hel(lowo)rld)"));
} ইনপুট
"(hel(lowo)rld)"
আউটপুট
13 0 0 0 9 0 0 0 0 4 0 0 0 0 dlrlowoleh
