পাইথনে ব্র্যাকেটের মধ্যে আবদ্ধ সাবস্ট্রিং উল্টে দেওয়ার প্রোগ্রাম

মান লইয়া যাই, আমাদের একটি লোয়ারকেস স্ট্রিং s আছে যাতে অক্ষর এবং পারেনথেসিস "(" এবং ")" রয়েছে। আমাদের পারেনথেসিসের মধ্যে আবদ্ধ প্রতিটি স্ট্রিংকে রিকারসিভ (recursive)ভাবে উল্টে দিতে হবে এবং ফলাফল স্ট্রিংটি রিটার্ন করতে হবে।

তবে, ইনপুট যদি s = "back(aps)ce" হয়, তবে আউটপুট হবে "backspace"।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• একটি trav() ফাংশন সংজ্ঞায়িত করুন। এটি s, dir, start, close:= close, ans:= ans প্যারামিটার গ্রহণ করবে

  • end := "(" যদি dir -1-এর সমান হয়, অন্যথায় ")"

  • other := "(" যদি end ")"-এর সমান হয়, অন্যথায় ")"

  • যখন start < s-এর আকার, এবং s[start] end-এর সমান নয়, তখন পর্যন্ত

    • যদি s[start] other-এর সমান হয়, তবে

      • trav(s, -dir, close[other, start] - dir) কল করুন

      • start := close[other, start] + dir

    • অন্যথায়,

      • s[start]-কে ans-এর শেষে ইনসার্ট করুন

      • start := start + dir

• মূল ফাংশন থেকে নিচের কাজগুলো করুন:

• ans := একটি নতুন লিস্ট

• close := একটি নতুন ম্যাপ যাতে ")" এবং "(" কী (key) হিসেবে থাকে, প্রাথমিকভাবে মান দুটি খালি ম্যাপ

• stack := একটি নতুন লিস্ট

• s-এ প্রতিটি ইন্ডেক্স i এবং মান c জন্য,

  • যদি c "("-এর সমান হয়, তবে

    • i-কে stack-এ পুশ করুন

  • অন্যথায় যখন c ")"-এর সমান হয়, তবে

    • o := stack-এর টপ, তারপর stack থেকে পপ করুন

    • close[")", i] := o

    • close["(", o] := i

• trav(s, 1, 0) কল করুন

• ans কে খালি স্ট্রিং দিয়ে জয়েন (join) করে রিটার্ন করুন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

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