मान लीजिए, हमारे पास एक लोअरकेस स्ट्रिंग है जिसमें अक्षर और कोष्ठक "(" और ")" हैं। हमें कोष्ठक के भीतर संलग्न प्रत्येक स्ट्रिंग को पुनरावर्ती तरीके से उलटना होगा और परिणामी स्ट्रिंग को वापस करना होगा।
इसलिए, यदि इनपुट s ="back(aps)ce" जैसा है, तो आउटपुट "बैकस्पेस" होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ट्रैव () फ़ंक्शन को परिभाषित करें। इसमें s, dir, start, close:=close, ans:=ans
. लगेगा-
अंत:="(" अगर डीआईआर -1 के समान है, अन्यथा ")"
-
अन्य :="(" यदि अंत ") के समान है", अन्यथा ")"
-
जबकि प्रारंभ
-
अगर s[शुरू] दूसरे के समान है, तो
-
ट्रैव (एस, -डीआईआर, बंद करें [अन्य, शुरू करें] - डीआईआर)
-
प्रारंभ:=बंद करें [अन्य, प्रारंभ करें] + डीआईआर
-
-
अन्यथा,
-
उत्तर के अंत में s[start] डालें
-
प्रारंभ:=प्रारंभ + डीआईआर
-
-
-
-
मुख्य कार्य से, निम्न कार्य करें -
-
उत्तर :=एक नई सूची
-
बंद करें:=एक नया नक्शा जिसमें कुंजियाँ हैं ")" और "(" शुरू में मान दो खाली नक्शे हैं
-
स्टैक :=एक नई सूची
-
प्रत्येक अनुक्रमणिका I और मान c के लिए s, करें
-
यदि c "(" के समान है, तो
-
मुझे स्टैक में पुश करें
-
-
अन्यथा जब c ")" के समान हो, तब
-
o:=स्टैक के ऊपर, फिर स्टैक से पॉप करें
-
बंद करें [")", i] :=o
-
बंद करें ["(", ओ]:=मैं
-
-
-
ट्रैव(एस, 1, 0)
-
वापसी उत्तर रिक्त स्ट्रिंग के साथ जुड़ गया
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution: def solve(self, s): ans = [] close = {")": {}, "(": {}} stack = [] for i, c in enumerate(s): if c == "(": stack.append(i) elif c == ")": o = stack.pop() close[")"][i] = o close["("][o] = i def trav(s, dir, start, close=close, ans=ans): end = "(" if dir == -1 else ")" other = "(" if end == ")" else ")" while start < len(s) and s[start] != end: if s[start] == other: trav(s, −dir, close[other][start] − dir) start = close[other][start] + dir else: ans.append(s[start]) start += dir trav(s, 1, 0) return "".join(ans) ob = Solution() print(ob.solve("back(aps)ce"))
इनपुट
"back(aps)ce"
आउटपुट
backspace