Kiểm tra dấu ngoặc cân bằng trong biểu thức với không gian O(1) và thời gian O(N²) trong Python

Cho một chuỗi str chứa các ký tự ngoặc '(', ')', '{', '}', '[' và ']'. Ta cần kiểm tra xem các ngoặc có cân bằng hay không. Các ngoặc được gọi là cân khi:

• Loại ngoặc mở và đóng phải cùng kiểu.
• Các ngoặc được đóng theo đúng thứ tự.

Ví dụ, nếu đầu vào là {([])} thì kết quả sẽ là True.

Thuật toán giải quyết

Để giải quyết bài toán này với độ phức tạp không gian O(1) và thời gian O(N²), ta thực hiện các bước sau:

• Khởi tạo cnt := 0, i := 0, j := -1.
• Định nghĩa hàm solve(s, temp):
  • cnt := cnt - 1.
  • Chuyển s thành danh sách mới.
  • Nếu j > -1 và s[j] == temp:
    • Gán s[i] := '#', s[j] := '#'.
    • Trong khi j >= 0 và s[j] == '#': giảm j.
    • Tăng i.
    • Trả về 1.
  • Ngược lại trả về 0.
• Từ hàm chính:
  • Nếu độ dài s bằng 0 thì trả về True.
  • Khác:
    • ans := False.
    • Trong khi i < len(s):
      • Nếu s[i] == '}': gọi solve(s, '{'). Nếu ans == 0 trả về False.
      • Ngược lại nếu s[i] == ')': gọi solve(s, '('). Nếu ans == 0 trả về False.
      • Ngược lại nếu s[i] == ']': gọi solve(s, '['). Nếu ans == 0 trả về False.
      • Ngược lại: j := i, i := i + 1, cnt := cnt + 1.
    • Nếu cnt != 0 trả về False.
    • Trả về True.

Ví dụ minh họa

cnt = 0
i = 0
j = -1

def solve(s, temp):
    global i, j, cnt
    cnt -= 1
    s = list(s)
    if j > -1 and s[j] == temp:
        s[i] = '#'
        s[j] = '#'
        while j >= 0 and s[j] == '#':
            j -= 1
        i += 1
        return 1
    else:
        return 0

def bracketOrderCheck(s):
    global i, j, cnt
    if len(s) == 0:
        return True
    else:
        ans = False
        while i < len(s):
            if s[i] == '}':
                ans = solve(s, '{')
                if ans == 0:
                    return False
            elif s[i] == ')':
                ans = solve(s, '(')
                if ans == 0:
                    return False
            elif s[i] == ']':
                ans = solve(s, '[')
                if ans == 0:
                    return False
            else:
                j = i
                i += 1
                cnt += 1
        if cnt != 0:
            return False
        return True

print(bracketOrderCheck("{([])}"))  # True

Đầu vào

"{(()[])}"

Đầu ra

True