मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें छोटे अक्षर और कोष्ठक होते हैं। हमें मिलान करने वाले कोष्ठकों के प्रत्येक जोड़े में, अंतरतम से शुरू करते हुए, स्ट्रिंग्स को उल्टा करना होगा। और परिणाम में कोई कोष्ठक नहीं होना चाहिए। तो यदि इनपुट "(हेल (लोवो) आरएलडी)" जैसा है, तो आउटपुट "डीएलआरलोवोलेह" होगा, इसलिए शुरुआत से, इसे इस तरह बदल दिया जाता है:"(हेल (लोवो) आरएलडी)" → "(हेलोवोलर्ड)" → "dlrowoleh"।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=स्ट्रिंग का आकार, एक सरणी बनाएं जिसे par कहा जाता है जिसकी लंबाई n है, एक स्टैक st परिभाषित करें
-
मेरे लिए 0 से n - 1 की सीमा में
-
अगर 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]
द्वारा रिट बढ़ाएं
-
-
वापसी रिट
उदाहरण (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