Chương trình tìm số nhóm ngoặc cân bằng tối đa trong Python

Cho chuỗi s chỉ chứa ngoặc đơn cân bằng, tách thành số nhóm cân bằng tối đa.

Ví dụ

Đầu vào: "(()())()(())".
Đầu ra: ['(()())', '()', '(())'].

Thuật toán

1. Khởi tạo temp = '', groups = [], count = 0.
2. Duyệt từng ký tự b:
   • Nếu count == 0 và temp không rỗng: thêm temp vào groups, reset temp.
   • Thêm b vào temp.
   • Nếu b == '(': count += 1; ngược lại: count -= 1.
3. Thêm temp cuối vào groups.
4. Trả về groups.

Mã nguồn Python

class Solution:
    def solve(self, s):
        temp = ''
        groups = []
        count = 0
        for b in s:
            if count == 0 and len(temp) > 0:
                groups.append(temp)
                temp = ''
            temp += b
            if b == '(':
                count += 1
            else:
                count -= 1
        groups.append(temp)
        return groups

s = "(()())()(())"
ob = Solution()
print(ob.solve(s))

Đầu vào / Đầu ra

Input: "(()())()(())"
Output: ['(()())', '()', '(())']