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
1function isPalindrome(s: string): boolean {2let left = 03let right = s.length - 14while (left < right) {5// Bỏ qua ký tự không phải chữ-số6while (left < right && !isAlphanumeric(s[left])) left++7while (left < right && !isAlphanumeric(s[right])) right--8if (s[left].toLowerCase() !== s[right].toLowerCase()) return false9left++10right--11}12return true13}14function isAlphanumeric(ch: string): boolean {16const code = ch.charCodeAt(0)17return (code >= 48 && code <= 57) // 0-918|| (code >= 65 && code <= 90) // A-Z19|| (code >= 97 && code <= 122) // a-z20}
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.