โปรแกรมกลับลำดับย่อยสตริงภายในวงเล็บใน Python

ให้สตริงที่มีตัวอักษรพิมพ์เล็กและวงเล็บ ต้องการกลับลำดับตัวอักษรภายในวงเล็บทุกคู่ แบบ recursive ตัวอย่าง: "back(aps)ce" → "backspace"

วิธีแก้

• สร้าง map close เก็บคู่ของวงเล็บเปิด-ปิดโดยใช้ stack
• ฟังก์ชัน trav เดินผ่านสตริง: เมื่อเจอวงเล็บ ให้เรียกตัวเองแบบ recursive พร้อมกลับทิศทาง
• รวบรวมตัวอักษรที่ไม่ใช่วงเล็บเข้า array ans

การนำไปใช้

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"))  # backspace