Valid Parentheses

Q: Độ phức tạp thời gian của bài toán ngoặc hợp lệ là bao nhiêu?

Giải pháp dùng ngăn xếp chạy trong thời gian O(n) , vì mỗi ký tự được đưa vào hoặc lấy ra khỏi ngăn xếp nhiều nhất một lần. Trong trường hợp xấu nhất, giải pháp dùng O(n) bộ nhớ, khi chuỗi chỉ có các dấu mở. Việc liên tục xóa các cặp khớp nhau mất O(n²) thời gian, vì mỗi lượt chuỗi lồng nhau sâu chỉ mất đi một cặp.

DễNgăn xếp

+10

Bạn nhận được một chuỗi s chỉ gồm các ký tự ngoặc (, ), [, ], { và }. Trả về true nếu các dấu ngoặc cân bằng: mỗi dấu ngoặc đóng khớp với dấu ngoặc mở gần nhất chưa được đóng, hai dấu ngoặc cùng loại và không còn dấu ngoặc nào chưa đóng ở cuối. Nếu không, trả về false.

Hàm

isValid(s: string) → boolean

sstring: chuỗi dấu ngoặc cần kiểm tra
Trả vềboolean: các dấu ngoặc có cân bằng hay không

Ràng buộc

1 ≤ s.length ≤ 10⁴
s chỉ chứa các ký tự (, ), [, ], { và }.

Ví dụ

Đầu vào: s = "[]{}()"
Đầu ra: true
Giải thích: Ba cặp đứng cạnh nhau, và mỗi cặp đóng ngay sau khi mở.

Đầu vào: s = "{(})"
Đầu ra: false
Giải thích: Ký tự } xuất hiện khi dấu ngoặc ( được mở sau đó vẫn chưa được đóng, nên nó đóng nhầm loại dấu ngoặc.

Câu hỏi mở rộng

Nếu chuỗi chỉ chứa dấu ngoặc đơn, bạn có thể kiểm tra chuỗi bằng một biến đếm duy nhất thay vì dùng ngăn xếp, với bộ nhớ phụ O(1) không?

Lời giải

Chỉ đếm dấu ngoặc là chưa đủ: {(}) có số lượng dấu mở và dấu đóng bằng nhau nhưng vẫn sai, vì thứ tự rất quan trọng. Ngăn xếp lưu các dấu ngoặc vẫn còn mở theo thứ tự chúng được mở, vì vậy chỉ cần duyệt chuỗi một lần bằng ngăn xếp là có thể xác định tính hợp lệ của toàn bộ chuỗi.

Liên tục xóa các cặp khớp nhau

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Mọi chuỗi cân bằng đều có một cặp trong cùng không có gì nằm giữa hai dấu ngoặc, như cặp () trong {[()]}. Xóa một cặp khớp liền kề không bao giờ làm thay đổi việc chuỗi có cân bằng hay không. Vì vậy, hãy lặp lại thao tác xóa cho đến khi có một lượt không xóa được gì: chuỗi cân bằng sẽ rút gọn thành chuỗi rỗng, còn chuỗi không cân bằng sẽ mắc kẹt với các ký tự còn lại, như trường hợp {(}) ngay từ đầu.

Mỗi lượt quét toàn bộ chuỗi và tạo một bản sao mới, còn một chuỗi lồng nhau như (((...))) sẽ mất một cặp sau mỗi lượt. Quá trình này có thể cần đến n/2 lượt, mỗi lượt tốn O(n) thao tác, tổng cộng là O(n²).

Thuật toán

Xóa mọi (), [] và {} trong chuỗi.
Nếu lần đó không xóa được gì, hãy dừng lại.
Nếu không, hãy lặp lại với chuỗi ngắn hơn.
Trả về true nếu chuỗi cuối cùng rỗng và false nếu còn lại bất kỳ dấu ngoặc nào.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Một lượt duyệt bằng ngăn xếp

Ý tưởng

Dấu ngoặc đóng phải đóng dấu ngoặc mở gần nhất vẫn chưa được đóng. Dấu ngoặc mở sau cùng sẽ được đóng trước, và thứ tự vào sau, ra trước này chính là cách ngăn xếp hoạt động.

Đẩy dấu ngoặc đóng tương ứng với mỗi dấu ngoặc mở vào ngăn xếp. Sau đó, dấu ngoặc đóng phải trùng với phần tử trên cùng của ngăn xếp. Ngăn xếp rỗng nghĩa là không có dấu ngoặc nào cần đóng; phần tử trên cùng khác loại nghĩa là dấu ngoặc đóng không đúng loại, như } trong {(}) khi ) đang ở trên cùng. Khi kết thúc, mọi thứ còn lại trên ngăn xếp, như trong ((, đều đã được mở nhưng chưa bao giờ được đóng. Mỗi ký tự được đẩy vào hoặc lấy ra khỏi ngăn xếp một lần: thời gian O(n), và ngăn xếp chứa tối đa n phần tử.

Thuật toán

Tạo một ngăn xếp rỗng.
Với dấu ngoặc mở, đẩy dấu ngoặc đóng tương ứng vào ngăn xếp.
Với dấu ngoặc đóng, trả về false nếu ngăn xếp rỗng hoặc phần tử trên cùng là ký tự khác; nếu không thì lấy phần tử đó ra.
Sau ký tự cuối cùng, chỉ trả về true nếu ngăn xếp rỗng.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Lỗi thường gặp và trường hợp biên

Đếm số lượng từng loại dấu ngoặc. {(}) có số lượng dấu ngoặc mở và đóng khớp nhau nhưng vẫn không hợp lệ, còn )( chỉ sai thứ tự.
Lấy phần tử khỏi ngăn xếp khi ngăn xếp đang trống. Chuỗi bắt đầu bằng dấu ngoặc đóng, chẳng hạn như } hoặc )]}, phải trả về false thay vì gây lỗi.
Bỏ qua bước kiểm tra cuối cùng. (([{ không gặp dấu ngoặc đóng sai nào, vì vậy chỉ ngăn xếp còn phần tử mới cho thấy chuỗi không hợp lệ.
Tin vào độ dài. Chuỗi có độ dài lẻ luôn không hợp lệ, nhưng độ dài chẵn không chứng minh được điều gì: (] và ())( đều không hợp lệ.
Trong cách tiếp cận bằng cách xóa, truyền dấu ngoặc vào biểu thức chính quy hoặc mẫu Lua mà không thoát ký tự. ( và [ có ý nghĩa đặc biệt ở đó; hãy dùng thao tác thay thế văn bản thuần.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán ngoặc hợp lệ là bao nhiêu?

Giải pháp dùng ngăn xếp chạy trong thời gian O(n), vì mỗi ký tự được đưa vào hoặc lấy ra khỏi ngăn xếp nhiều nhất một lần. Trong trường hợp xấu nhất, giải pháp dùng O(n) bộ nhớ, khi chuỗi chỉ có các dấu mở. Việc liên tục xóa các cặp khớp nhau mất O(n²) thời gian, vì mỗi lượt chuỗi lồng nhau sâu chỉ mất đi một cặp.

Tại sao ngăn xếp được dùng để kiểm tra dấu ngoặc hợp lệ?

Dấu ngoặc lồng nhau, vì vậy dấu ngoặc được mở sau cùng phải được đóng trước tiên. Ngăn xếp giữ dấu ngoặc đó ở trên cùng, nơi bạn có thể đọc và xóa nó trong thời gian hằng số, nhờ đó toàn bộ quá trình kiểm tra có độ phức tạp O(n).

Chuỗi rỗng có phải là dấu ngoặc hợp lệ không?

Đúng vậy. Chuỗi rỗng không có dấu ngoặc nào không được ghép cặp, nên chuỗi này cân bằng: ngăn xếp vẫn rỗng và vòng lặp xóa không có gì để xóa. Trong bài toán này, s luôn có ít nhất một ký tự.

def isValid(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "[]{}()"

Đầu ra mong đợi

true