Xác Nhận PalindromeValid Palindrome
Hiểu bài
Cho bạn một chuỗi s. Sau khi chuyển tất cả ký tự hoa thành thường và loại bỏ ký tự không phải chữ-số, hãy kiểm tra xem chuỗi còn lại có phải palindrome không — tức là đọc xuôi và ngược đều giống nhau.
Ví dụ:
s = "A man, a plan, a canal: Panama"
output = true // sau khi làm sạch: "amanaplanacanalpanama" — đọc xuôi ngược giống nhau
s = "race a car"
output = false // sau khi làm sạch: "raceacar" — khác nhauKỹ thuật Hai con trỏ (Two-Pointer) xử lý tại chỗ mà không cần tạo chuỗi mới — O(1) space thực sự.
Xem cách cơ bản (chậm hơn)
O(n) time, O(n) spacefunction isPalindrome(s: string): boolean {
// Lọc và chuẩn hóa chuỗi
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}Tạo chuỗi cleaned và chuỗi đảo ngược — mỗi cái tốn O(n) space.
Cách đơn giản nhưng tốn bộ nhớ không cần thiết.
Lời giải tối ưu
O(n) time, O(1) spacefunction isPalindrome(s: string): boolean {
let left = 0
let right = s.length - 1
while (left < right) {
// Bỏ qua ký tự không phải chữ-số
while (left < right && !isAlphanumeric(s[left])) left++
while (left < right && !isAlphanumeric(s[right])) right--
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false
left++
right--
}
return true
}
function isAlphanumeric(ch: string): boolean {
const code = ch.charCodeAt(0)
return (code >= 48 && code <= 57) // 0-9
|| (code >= 65 && code <= 90) // A-Z
|| (code >= 97 && code <= 122) // a-z
}Cách tối ưu: hai con trỏ tiến vào giữa, mỗi bước nhảy qua ký tự không hợp lệ.
- Không tạo chuỗi mới — xử lý trực tiếp trên chuỗi gốc.
- Dừng khi 2 con trỏ gặp nhau.
Chạy thử từng bước
- 1
s="a,bba". left=0 ('a'), right=4 ('a') — cả hai là chữ-số, 'a'='a' khớp → tiến vào trong.
left:0right:4leftChar:"a"rightChar:"a"action:"khớp → vào trong" - 2
left=1 trỏ ',' (không phải chữ-số) → nhảy qua: left=2 ('b').
So sánh 'b' (index 2) với 'b' (index 3): khớp.
left:2right:3leftChar:"b"rightChar:"b"action:"skip dấu phẩy → khớp" - 3
Sau khi tiến tiếp, left
- vượt right
- → hai con trỏ gặp/vượt nhau, đã duyệt hết mà không gặp mismatch → return true
left:3right:2result:true
Trường hợp biên phải nhớ
Chuỗi rỗng — sau khi lọc không có ký tự nào, return true (palindrome rỗng).
Chỉ có ký tự đặc biệt "!!! ???" — sau lọc là chuỗi rỗng, return true.
Một ký tự alphanumeric "a" — left=right=0, vòng lặp while (left < right) không chạy, return true.
Tất cả ký tự không phải alphanumeric xen kẽ giữa palindrome: "A.,B" → cleaned "ab" → không phải palindrome.