LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Valid Palindrome

Bandingkan karakter dari kedua ujung sambil melewati tanda baca dan mengabaikan huruf besar kecil.

Di artikel ini 7 bagian

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:

javascript
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

javascript
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

  1. Off by one error: Pastikan kondisi loop kamu left < right (bukan <=) supaya karakter tengah nggak dicek dua kali
  2. Edge case: String kosong dan string satu karakter itu palindrome menurut definisinya
  3. 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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan