Untuk pengecekan palindrome ini, aku membandingkan karakter dari kedua ujung lalu bergerak ke dalam. Karakter yang berbeda menghentikan pencarian; pasangan yang cocok membuatnya lanjut tanpa membuat salinan string terbalik.
Memahami Soalnya
LeetCode 125 memakai input berupa karakter ASCII yang printable. Abaikan tanda baca dan spasi, lalu bandingkan huruf tanpa membedakan huruf besar dan kecil. Digit tetap ikut dibandingkan. Contohnya, "A man, a plan, a canal: Panama" valid, sedangkan "race a car" nggak.
Membalik salinan yang dinormalisasi
Versi pertama menghapus karakter yang bukan alfanumerik dan mengubah huruf jadi lowercase. Setelah itu hasilnya dibalik, lalu kedua string dibandingkan:
function isPalindromeNaive(s) {
const normalized = s.toLowerCase().replace(/[^a-z0-9]/g, "");
const reversed = normalized.split("").reverse().join("");
return normalized === reversed;
}
String yang dinormalisasi dan string yang dibalik memakai extra space O(n). Versi two pointer langsung mengecek input aslinya.
Membandingkan kedua ujung
Teknik two pointers cocok di sini karena palindrome itu simetris. Kalau karakter di kedua ujung cocok, aku bisa bergerak ke tengah dan mengecek pasangan berikutnya. Kalau nggak cocok, aku tahu itu bukan palindrome.
Implementasi two pointer
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
// Skip characters that the problem excludes from comparison.
while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
while (left < right && !/[a-z0-9]/i.test(s[right])) right--;
if (left >= right) break;
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
// Move both pointers inward
left++;
right--;
}
return true; // All characters matched!
}
Trace pointer
Untuk "racecar", pointer-nya bergerak seperti ini:
- Awal: left=0 ('r'), right=6 ('r')
- Karakternya cocok, jadi bergerak ke tengah: left=1, right=5
- left=1 ('a'), right=5 ('a'): cocok! Bergerak ke tengah: left=2, right=4
- left=2 ('c'), right=4 ('c'): cocok! Bergerak ke tengah: left=3, right=3
- left >= right, keluar dari loop
- Return true!
Waktu dan ruang
Space Complexity: O(1)
- Nggak ada salinan input yang dinormalisasi secara utuh
- Cuma pakai dua variabel integer untuk pointer
Time Complexity: O(n)
- Satu pass di sepanjang string
- Tiap pointer bergerak ke satu arah, jadi total kerjanya O(n)
- Berpotensi lebih cepat daripada membalik string karena kita bisa berhenti lebih awal kalau ketemu karakter yang nggak cocok
Kesalahan yang Sering Terjadi
- Off by one error: Pastikan kondisi loop kamu
left < right(bukan<=) supaya karakter tengah nggak dicek dua kali - Edge case: String kosong dan string satu karakter itu palindrome menurut definisinya
- Aturan input: Abaikan tanda baca dan spasi. Bandingkan huruf tanpa membedakan huruf besar dan kecil, dan tetap sertakan digit.
Aturan karakter ini mengikuti input ASCII di soal. Pengecekan untuk teks Unicode umum perlu keputusan yang jelas soal normalisasi dan apa yang dianggap satu karakter.

Memuat komentar...