ধরুন আমাদের একটি স্ট্রিং s আছে যা ছোট হাতের অক্ষর এবং ব্র্যাকেট সম্বহ করে। আমাদের প্রতিটি মিলিত প্যারেনথেসিস জোড়ার মধ্যবর্তী স্ট্রিংগুলো রিভার্স করতে হবে, ইনারমোস্ট থেকে শুরু করে। ফলাফলে কোনো ব্র্যাকেট থাকবে না। যেন ইনপুট "(hel(lowo)rld)" হয়, তবে আউটপুট হবে "dlrlowoleh", কারণ পরিবর্তনটি হবে: "(hel(lowo)rld)" → "(helowolrld)" → "dlrowoleh"
সমাধান পদ্ধতি
- n := স্ট্রিং আকার, panjang n-এর একটি par অ্যারে বানান, একটি স্ট্যাক st ডিফাইন করুন
- i = 0 থেকে n-1 পর্যন্ত লুপ চালান
- যদি s[i] ওপেনিং প্যারেনথেসিস হয়, তবে i-কে st-এ পুশ করুন
- অন্যথায় যখন s[i] ক্লোজিং প্যারেনথেসিস হয়, তবে j := st.pop(), par[i] := j এবং par[j] := i
- একটি খালি স্ট্রিং ret ডিফাইন করুন
- i := 0, d := 1, i < n, i += d-র জন্য লুপ চালান
- যদি s[i] ওপেনিং বা ক্লোজিং প্যারেনথেসিস হয়, তবে i := par[i], d := -d; অন্যথায় ret-এ 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; } }; int 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
