Chương trình tìm số dấu ngoặc tối thiểu cần xóa để chuỗi hợp lệ trong Python

Mô tả bài toán

Cho chuỗi s chứa dấu ngoặc '(', ')' và chữ cái thường. Hãy xóa số lượng dấu ngoặc tối thiểu để chuỗi kết quả hợp lệ. Chuỗi ngoặc hợp lệ khi: rỗng/chỉ chứa chữ cái; hoặc dạng AB (A, B hợp lệ); hoặc dạng (A) (A hợp lệ).

Ví dụ

Nếu đầu vào là s = "m)n(o)p", thì đầu ra sẽ là "mn(o)p".

Giải thuật

1. Dùng stack lưu chỉ số của '(', tập hợp indexes lưu chỉ số cần xóa.
2. Duyệt chuỗi: gặp '(' đẩy chỉ số vào stack; gặp ')' nếu stack rỗng thì thêm chỉ số vào indexes, ngược lại pop stack.
3. Hợp nhất indexes với các chỉ số còn lại trong stack.
4. Xây dựng chuỗi kết quả bỏ qua các chỉ số trong indexes.

Triển khai Python

def solve(s):
    stack = []
    indexes = set()
    i = 0
    for c in s:
        if c == '(':
            stack.append(i)
        elif c == ')':
            if len(stack) == 0:
                indexes.add(i)
            else:
                stack.pop()
        i += 1
    ret = ''
    indexes = indexes.union(stack)
    for i in range(len(s)):
        if i not in indexes:
            ret += s[i]
    return ret

s = "m)n(o)p"
print(solve(s))

Đầu vào

"m)n(o)p"

Đầu ra

mn(o)p