मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें लोअरकेस लेटर्स और ब्रैकेट्स हैं। हमें मैचिंग पैरेंथेसिस के प्रत्येक जोड़े में स्ट्रिंग्स को रिवर्स करना है, इनरमोस्ट से शुरू करके। और रिजल्ट में कोई ब्रैकेट नहीं होना चाहिए। उदाहरण के लिए, अगर इनपुट है "(hel(lowo)rld)", तो आउटपुट होगा "dlrlowoleh", क्योंकि शुरुआत से यह ऐसे बदलता है: "(hel(lowo)rld)" → "(helowolrld)" → "dlrowoleh"।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
n := स्ट्रिंग का साइज, par नाम का एक ऐरे बनाएं जिसकी लंबाई n हो, एक स्टैक 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] ओपनिंग पैरेंथेसिस है या 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