Chương trình đảo ngược chuỗi con nằm trong ngoặc đơn trong Python

Cho chuỗi chữ thường s chứa chữ cái và ngoặc '(' ')'. Cần đảo ngược mọi chuỗi con nằm trong ngoặc đơn theo cách đệ quy và trả về chuỗi kết quả.

Ví dụ: s = "back(aps)ce" -> "backspace".

Giải pháp: dùng stack tìm cặp ngoặc khớp, sau đó duyệt đệ quy với hướng thay đổi khi gặp ngoặc lồng nhau.

Ví dụ

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

Đầu vào

"back(aps)ce"

Đầu ra

backspace