Kiểm tra dấu ngoặc hợp lệ (Valid Parentheses) bằng stack — vì sao stack là cấu trúc đúng?

Ý tưởng: Quét chuỗi, gặp ngoặc mở thì push, gặp ngoặc đóng thì pop và kiểm tra có khớp loại không. Cuối cùng stack rỗng mới hợp lệ.

Vì sao stack: quy tắc khớp ngoặc là LIFO — ngoặc mở gần nhất phải đóng trước. Đó đúng là bản chất của stack.

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
  const stack: string[] = []
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch)
    else if (stack.pop() !== pairs[ch]) return false
  }
  return stack.length === 0
}

Độ phức tạp: thời gian O(n), bộ nhớ O(n) (xấu nhất toàn ngoặc mở).

Lưu ý: Hai bẫy hay quên —

1. stack rỗng mà gặp ngoặc đóng (pop() trả undefined, vẫn xử đúng nhờ so sánh khác)
2. cuối vòng còn ngoặc mở chưa đóng nên phải check stack.length === 0