Valid Parentheses

Bài toán

Cho một chuỗi s chỉ chứa các ký tự (, ), {, }, [, ]. Xác định xem chuỗi đầu vào có hợp lệ hay không. Hợp lệ khi:

1. Dấu mở phải được đóng bằng cùng loại dấu đóng tương ứng.
2. Dấu mở phải được đóng theo đúng thứ tự.

Ví dụ:

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Input: s = "{[]}"
Output: true

Phân Tích & Tiếp Cận

Logic: Last In, First Out (LIFO)

Đây là đặc tính của Stack (Ngăn xếp).

• Khi gặp dấu mở (( [ {): Ta chưa biết khi nào nó sẽ đóng, nên ta "đẩy" nó vào ngăn xếp để chờ.
• Khi gặp dấu đóng () ] }): Dấu này BẮT BUỘC phải khớp với dấu mở gần nhất vừa được thêm vào ngăn xếp.
  • Nếu ngăn xếp rỗng -> Lỗi (Dư dấu đóng).
  • Nếu phần tử trên đỉnh ngăn xếp không khớp cặp -> Lỗi.
  • Nếu khớp -> Hủy cặp (Pop khỏi ngăn xếp).

Sau cùng, ngăn xếp phải rỗng (tất cả dấu mở đều đã được đóng).

function isValid(s: string): boolean {
    // Stack để lưu các dấu mở
    const stack: string[] = [];
    
    // Map quy định cặp đóng-mở
    const bracketMap: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (const char of s) {
        // Nếu là dấu đóng (vì nó là key trong map)
        if (char in bracketMap) {
            // Lấy dấu mở ở đỉnh stack
            // Nếu stack rỗng, pop() trả về undefined -> Không khớp
            const topElement = stack.pop();

            if (topElement !== bracketMap[char]) {
                return false;
            }
        } 
        // Nếu là dấu mở
        else {
            stack.push(char);
        }
    }

    // Stack phải rỗng mới là hợp lệ
    return stack.length === 0;
}

• Time Complexity: $O(n)$ - Duyệt chuỗi 1 lần. Push/Pop là $O(1)$.
• Space Complexity: $O(n)$ - Trường hợp xấu nhất ((((( thì stack chứa toàn bộ chuỗi.

Pattern Nhận Diện

Khi gặp bài toán yêu cầu xử lý các cặp phần tử có tính chất lồng nhau (nested) hoặc yêu cầu xử lý ngược thời gian (gần nhất xử lý trước), hãy nghĩ ngay đến Stack. Ví dụ:

• Undo/Redo (Lệnh mới nhất undo trước).
• Browser History (Back button).
• Call Stack (Hàm gọi sau kết thúc trước).