Valid Parentheses: LIFO là chính xác thứ mà ngoặc khớp cần

Trước khi chọn cấu trúc dữ liệu, hãy hỏi bài toán thực sự yêu cầu gì. Ở đây: bạn đang đọc một chuỗi từ trái sang phải, và mỗi khi gặp ngoặc đóng, bạn cần biết ngoặc mở gần nhất là gì. Không phải cái đầu tiên. Không phải bất kỳ cái nào. Cái gần nhất.

Đó là LIFO theo định nghĩa. Stack không phải là thủ thuật — nó là bản dịch trực tiếp của ràng buộc đó vào code.

Bài toán: cho một chuỗi chỉ chứa (, ), {, }, [, ], kiểm tra xem nó có hợp lệ không. Hợp lệ nghĩa là mỗi ngoặc mở được đóng bởi cùng loại, theo đúng thứ tự, và mỗi ngoặc đóng có một ngoặc mở tương ứng. Hai constraints làm hết việc. 1 <= s.length <= 10^4 thực tế loại bỏ O(n²) (dù với n = 10,000 một thuật toán bậc hai vẫn chạy được, chỉ là kém hiệu quả). s chỉ chứa sáu ký tự ngoặc, nên bạn không bao giờ cần xử lý gì khác — mapping cố định ở ba cặp.

Brute force: O(n²)

Có một cách brute force hoạt động được: liên tục quét để tìm các cặp khớp liền kề — (), [], {} — và xóa chúng cho đến khi không còn thay đổi. Nếu chuỗi rỗng ở cuối, nó hợp lệ.

class Solution:
    def isValid(self, s: str) -> bool:
        while "()" in s or "[]" in s or "{}" in s:
            s = s.replace("()", "")
            s = s.replace("[]", "")
            s = s.replace("{}", "")
        return len(s) == 0

public class Solution {
    public bool IsValid(string s) {
        while (s.Contains("()") || s.Contains("[]") || s.Contains("{}")) {
            s = s.Replace("()", "");
            s = s.Replace("[]", "");
            s = s.Replace("{}", "");
        }
        return s.Length == 0;
    }
}

Nó hoạt động với mọi ví dụ trong đề. Nhưng xét (((()))): mỗi lượt replace chỉ loại được một cặp trong cùng, cần bốn lượt cho chuỗi dài 8. Mỗi lần Replace tạo một string mới, tức là bạn đang tiêu tốn O(n) memory cho mỗi lượt với tới n/2 lượt — O(n²) time, O(n) space cho tất cả các allocation trung gian.

Quan trọng hơn, cách này chống lại cấu trúc của bài toán thay vì sử dụng nó. Bài toán có tính lồng nhau. Brute force xóa sự lồng nhau từ ngoài vào trong. Stack xử lý từ trong ra ngoài — đúng với ràng buộc thực tế.

Giải pháp stack: O(n)

Một lượt duyệt. Với mỗi ký tự:

• Ngoặc mở ((, [, {): push vào stack.
• Ngoặc đóng (), ], }): đỉnh stack phải là ngoặc mở tương ứng. Nếu stack rỗng hoặc đỉnh không khớp, chuỗi không hợp lệ. Pop và tiếp tục.

Sau vòng lặp, chuỗi hợp lệ chỉ khi stack rỗng — tức là mọi ngoặc mở đều đã được khớp và tiêu thụ.

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {")": "(", "]": "[", "}": "{"}
        stack = []
 
        for char in s:
            if char in mapping:
                top = stack.pop() if stack else "#"
                if mapping[char] != top:
                    return False
            else:
                stack.append(char)
 
        return not stack

public class Solution {
    public bool IsValid(string s) {
        var mapping = new Dictionary<char, char> {
            { ')', '(' },
            { ']', '[' },
            { '}', '{' }
        };
        var stack = new Stack<char>();
 
        foreach (char c in s) {
            if (mapping.ContainsKey(c)) {
                char top = stack.Count > 0 ? stack.Pop() : '#';
                if (mapping[c] != top) return false;
            } else {
                stack.Push(c);
            }
        }
 
        return stack.Count == 0;
    }
}

O(n) time — một lượt duyệt, mỗi push và pop là O(1). O(n) space — trong trường hợp xấu nhất, một chuỗi toàn ngoặc mở ((((() sẽ lấp đầy stack trước khi bất kỳ ngoặc đóng nào xuất hiện.

Key của mapping là các ngoặc đóng. Khi gặp ), bạn tra cứu ngoặc mở tương ứng ( và so sánh với phần tử vừa pop. Dùng ngoặc đóng làm key là lựa chọn đúng: bạn chỉ cần map trong quyết định pop, không phải trong push.

Trace tay qua hai ví dụ

Ví dụ: ([{}]) — nên trả về true.

Trạng thái sau khi xử lý mỗi ký tự:

Từng bước chi tiết:

char='('  -> ngoặc mở -> stack=['(']
char='['  -> ngoặc mở -> stack=['(', '[']
char='{'  -> ngoặc mở -> stack=['(', '[', '{']
char='}'  -> ngoặc đóng, mapping['}']='{'  top='{' -> khớp, pop -> stack=['(', '[']
char=']'  -> ngoặc đóng, mapping[']']='['  top='[' -> khớp, pop -> stack=['(']
char=')'  -> ngoặc đóng, mapping[')']='('  top='(' -> khớp, pop -> stack=[]
Kết thúc: stack rỗng -> return True

Cặp trong cùng đóng trước. Đó là toàn bộ ý tưởng. Tính LIFO của stack tự nhiên thực thi yêu cầu lồng nhau mà không cần bất kỳ logic đặc biệt nào.

Ví dụ: ([)] — nên trả về false.

char='('  -> ngoặc mở -> stack=['(']
char='['  -> ngoặc mở -> stack=['(', '[']
char=')'  -> ngoặc đóng, mapping[')']='('  top='[' -> không khớp -> return False

Lỗi bị phát hiện ngay tại ký tự thứ ba. Bạn mở [ gần nhất, nhưng lại cố đóng ( trước khi đóng [. Stack phát hiện ra vì đỉnh là [, không phải (.

Các edge case, mỗi cái đều được tính đến

Stack rỗng khi gặp ngoặc đóng. Bạn gặp ) nhưng stack không có gì. Không có ngoặc mở nào để khớp. Python xử lý bằng stack.pop() if stack else "#" — sentinel "#" sẽ không bao giờ bằng bất kỳ ký tự ngoặc nào, nên mapping[char] != top bắn True và bạn return False ngay. Trong C#, ternary stack.Count > 0 ? stack.Pop() : '#' làm điều tương tự. Đừng gọi pop() vô điều kiện — bạn sẽ nhận InvalidOperationException trong C# hoặc IndexError trong Python.

Stack không rỗng ở cuối. ((( push ba lần và không bao giờ pop. Vòng lặp kết thúc sạch sẽ, nhưng return not stack là False vì ba ngoặc mở chưa được khớp vẫn còn đó. Lỗi phổ biến là return True vô điều kiện ở cuối — sẽ pass hầu hết các ví dụ nhưng fail mọi chuỗi chỉ toàn ngoặc mở.

Chuỗi toàn ngoặc đóng. ))) gặp stack rỗng ngay tại ký tự đầu tiên và return False tức thì. Không cần xử lý đặc biệt; sentinel empty-stack đã cover.

Thứ tự lồng nhau sai. ([)] — đã cover ở trace trên. Đỉnh stack luôn là ngoặc mở được mở gần nhất, nên một cross-close như thế này bị bắt ngay khi ngoặc đóng sai xuất hiện.

Độ dài lẻ. Bất kỳ chuỗi nào có độ dài lẻ đều chắc chắn không hợp lệ — bạn không thể ghép cặp số lẻ ngoặc. Kiểm tra if len(s) % 2 == 1: return False ngay từ đầu giảm một nửa input trước vòng lặp. Code hiện tại xử lý đúng mà không cần check này (stack sẽ không rỗng ở cuối), nhưng thêm nó là một early-exit optimization đáng đề cập trong interview.

Ký tự đơn. ( push một lần và kết thúc với stack kích thước 1 — not stack là False. ) gặp sentinel stack rỗng và return False ngay lập tức.

Tại sao stack là fit tự nhiên, không chỉ là fit hợp lệ

Xét ([{}]). Cặp trong cùng {} đóng trước. Rồi []. Rồi (). Mỗi loại ngoặc đóng theo thứ tự ngược với thứ tự mở. Đó chính là định nghĩa của chuỗi pop của một stack.

So sánh với queue — first-in-first-out. Queue sẽ pop ( khi bạn cố khớp {. Điều đó sai về mặt cấu trúc. Cấu trúc dữ liệu và ràng buộc của bài toán được căn chỉnh ở mức độ khái niệm, không chỉ ở mức độ implementation. Đó là điều bạn muốn nhận ra và giải thích trong interview.

Tôi sẽ ship giải pháp stack mà không do dự. Brute force ổn như bằng chứng về concept, nhưng việc tạo string liên tục và hành vi O(n²) khiến nó không phù hợp với bất kỳ input thực tế nào. Phiên bản stack chạy trong thời gian tuyến tính, dùng một mapping kích thước cố định, và code đủ ngắn để viết từ trí nhớ.

So sánh các approach

Cả hai đều dùng O(n) space nhưng vì lý do khác nhau. Brute force tạo string mới nhiều lần. Giải pháp stack dùng O(n) stack space — không tránh được, vì bạn có thể cần giữ tất cả ngoặc mở trước khi thấy ngoặc đóng nào.

Nhận diện pattern

Nghĩ đến stack khi:

• Bài toán liên quan đến matching hoặc pairing các phần tử (ngoặc, tags, quotes, function calls).
• Thứ tự pairing quan trọng: cái mở gần nhất phải được đóng trước tiên.
• Keywords trong đề bài: "valid", "balanced", "matching", "nested", "parentheses".

Đây là bracket-matching pattern. Khi nhận ra nó, giải pháp stack theo đến một cách cơ học: push openers, pop và verify khi gặp closers, check empty ở cuối.

Các bài liên quan

LeetCode 22 — Generate Parentheses: sinh tất cả combinations của n cặp ngoặc hợp lệ. Backtracking với bộ đếm open/close — insight về tính hợp lệ từ bài này được áp dụng trực tiếp.

LeetCode 32 — Longest Valid Parentheses: tìm độ dài chuỗi con ngoặc hợp lệ dài nhất. Khó hơn. Stack của các index thay vì ký tự; twist là theo dõi các vị trí bắt đầu.

LeetCode 301 — Remove Invalid Parentheses: xóa số ít nhất ngoặc để chuỗi hợp lệ. BFS hoặc backtracking — bạn cần khám phá xem nên xóa những ngoặc nào.

LeetCode 921 — Minimum Add to Make Parentheses Valid: đếm số ngoặc cần thêm vào. Theo dõi open và close imbalances trong một lượt — không cần stack, chỉ hai bộ đếm.

LeetCode 1021 — Remove Outermost Parentheses: loại bỏ lớp ngoài cùng của mỗi nhóm hợp lệ. Biến thể dùng depth counter của chính vòng lặp đọc ngoặc này.

Những bài tiếp theo trong series này

Bài này giới thiệu stack pattern. Các bài tiếp theo cho thấy pattern đó mở rộng với các ràng buộc khó hơn:

Min Stack (155) — stack phải trả lời getMin() trong O(1). Bạn duy trì một stack thứ hai theo dõi giá trị nhỏ nhất tại mỗi mức, cập nhật khi mỗi lần push.

Daily Temperatures (739) — tìm bao nhiêu ngày nữa thì nhiệt độ ấm hơn. Một monotonic stack của các index, nơi bạn pop khi nhiệt độ hiện tại vượt quá nhiệt độ tại index được lưu.

Evaluate Reverse Polish Notation (150) — xử lý biểu thức postfix. Toán hạng đẩy vào stack; mỗi toán tử pop hai toán hạng, áp dụng phép tính, push kết quả. Cùng hình dạng push-khi-mở, pop-khi-đóng — chỉ với số và toán tử thay vì ngoặc.

Mỗi bài thêm một ràng buộc mà brute force không thể hấp thụ gọn gàng. Stack hấp thụ tất cả.