Ngoặc Hợp LệValid Parentheses
Hiểu bài
Cho chuỗi s chỉ gồm các ký tự ()[]{}.
Trả về true nếu chuỗi đóng-mở ngoặc hợp lệ: mỗi ngoặc mở có một ngoặc đóng cùng loại, và đóng đúng thứ tự.
s = "()[]{}" → true
s = "([])" → true // lồng nhau đúng
s = "(]" → false // sai loại
s = "([)]" → false // sai thứ tự lồngÝ chính: ngoặc mở gần nhất phải được đóng trước. "Gần nhất, xử lý trước" chính là tính chất LIFO của ngăn xếp (stack).
Xem cách cơ bản (chậm hơn)
O(n²) time, O(n) spacefunction isValidNaive(s: string): boolean {
let prev = ''
// Xoá dần các cặp liền kề "()", "[]", "{}" cho tới khi không xoá được nữa
while (prev !== s) {
prev = s
s = s.replace('()', '').replace('[]', '').replace('{}', '')
}
return s.length === 0
}Mỗi lần replace quét lại gần như toàn chuỗi, và phải lặp tới khi chuỗi không đổi.
Chuỗi dạng "(((...)))" làm số vòng lặp tỉ lệ với độ dài → O(n²).
Lời giải tối ưu
O(n) time, O(n) spacefunction isValid(s: string): boolean {
const stack: string[] = []
const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
for (const ch of s) {
if (ch === '(' || ch === '[' || ch === '{') {
stack.push(ch)
} else {
// ký tự đóng: đỉnh ngăn xếp phải là ký tự mở khớp
// stack rỗng → trả ngay false (đóng mà không có mở trước)
if (!stack.length || stack.pop() !== pairs[ch]) return false
}
}
return stack.length === 0
}Cách tối ưu: gặp ngoặc mở thì đẩy vào ngăn xếp; gặp ngoặc đóng thì lấy đỉnh ra so khớp — đỉnh chính là ngoặc mở gần nhất chưa đóng.
- Sai loại hoặc ngăn xếp rỗng khi pop → không hợp lệ.
- Cuối cùng ngăn xếp phải rỗng (không còn ngoặc mở thừa).
Chạy thử từng bước
- 1
s="([])". ch="(" là ngoặc mở → push. stack=["("].
ch:"("stack:["("] - 2
ch="[" là ngoặc mở → push. stack=["(","["].
ch:"["stack:["(","["] - 3
ch="]" là đóng. pop()="[" === pairs["]"]="[" → khớp. stack=["("].
ch:"]"popped:"["stack:["("] - 4
ch=")" là đóng. pop()="(" === pairs[")"]="(" → khớp. stack=[].
ch:")"popped:"("stack:[] - 5
Hết chuỗi. stack rỗng → trả về true.
stack:[]result:true
Trường hợp biên phải nhớ
Chuỗi rỗng "" → ngăn xếp rỗng → true.
Chỉ một ngoặc mở "(" → cuối cùng stack còn phần tử → false.
Bắt đầu bằng ngoặc đóng ")" → pop() trên stack rỗng trả về undefined ≠ pairs → false.
Số ngoặc lẻ → chắc chắn không khớp hết → false.