Valid Palindrome

Q: Berapa kompleksitas waktu Valid Palindrome?

Kedua pendekatan berjalan dalam waktu O(n) , karena setiap karakter diperiksa sejumlah kali yang konstan. Membersihkan terlebih dahulu menggunakan memori tambahan O(n) untuk salinannya. Versi dua pointer menggunakan memori tambahan O(1) , karena hanya menyimpan dua indeks.

Q: Apakah string kosong merupakan palindrome?

Ya. Teks kosong terbaca sama dari kedua arah, jadi string seperti ?!-_ , yang semua karakternya diabaikan, mengembalikan true . Kedua pendekatan mendapatkan hasil ini tanpa kode tambahan: teks yang sudah dibersihkan sama dengan kebalikannya yang kosong, dan kedua pointer tidak pernah menemukan pasangan yang berbeda.

Q: Mengapa menggunakan dua pointer alih-alih membalik string?

Membalik membutuhkan salinan yang sudah dibersihkan dan salinan yang dibalik, sehingga memerlukan memori tambahan O(n) . Dua pointer membandingkan pasangan yang sama secara langsung, lalu berhenti saat menemukan ketidakcocokan pertama, sering kali hanya setelah beberapa langkah.

MudahTwo pointers

+10

Kamu mendapatkan sebuah string s. Pertahankan hanya huruf dan angkanya, anggap huruf besar dan huruf kecil sebagai huruf yang sama, lalu tentukan apakah hasilnya sama jika dibaca dari kiri ke kanan maupun dari kanan ke kiri. Kembalikan true jika ya dan false jika tidak.

Semua karakter lainnya, seperti ., !, ?, :, ;, -, atau _, diabaikan. Jika s sama sekali tidak memiliki huruf atau angka, tidak ada yang tersisa, dan teks kosong dianggap sebagai palindrom.

Fungsi

isPalindrome(s: string) → boolean

sstring: teks yang perlu diperiksa, termasuk tanda baca
Mengembalikanboolean: benar jika huruf dan angka pada s dibaca sama dari kedua arah, tanpa membedakan huruf besar dan kecil

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s berisi huruf bahasa Inggris, angka, dan tanda baca . ! ? : ; - _, tanpa spasi.

Contoh

Input: s = "Was_it_a_car_or_a_cat_I_saw?"
Output: true
Penjelasan: Hilangkan garis bawah dan tanda tanya, lalu ubah huruf kapital menjadi huruf kecil: hasilnya wasitacaroracatisaw, yang sama jika dibaca terbalik.

Input: s = "race-a-car"
Output: false
Penjelasan: Tanpa tanda hubung, teksnya adalah raceacar. e di tengah memiliki a sebagai pasangan cerminnya, jadi jawabannya adalah false.

Input: s = "Step-on-no-pets!"
Output: true
Penjelasan: Teks yang dipertahankan adalah steponnopets. Huruf kapital S cocok dengan s terakhir karena kapitalisasi diabaikan, dan tanda hubung serta ! tidak berperan.

Pertanyaan lanjutan

Bisakah kamu menentukan ini dengan memori tambahan O(1), tanpa membuat salinan s yang sudah dibersihkan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Pemeriksaannya seperti biasa: karakter pertama yang dipertahankan harus sama dengan karakter terakhir, karakter kedua harus sama dengan karakter kedua dari belakang, dan seterusnya. Masalahnya, karakter yang dipertahankan tidak berada pada indeks yang berlawanan di s, karena tanda baca tersebar tidak merata. Hapus tanda baca terlebih dahulu, atau biarkan dua pointer melewatinya saat bergerak ke arah dalam.

Bersihkan string, lalu bandingkan dengan kebalikannya

Intuisi

Telusuri s, pertahankan setiap huruf atau angka dalam huruf kecil, dan abaikan sisanya: Step-on-no-pets! menjadi steponnopets. Pembersihan menghapus tepat hal-hal yang menurut soal harus diabaikan, jadi jawabannya adalah apakah teks ini sama dengan kebalikannya. string tanpa huruf atau angka akan dibersihkan menjadi teks kosong, yang sama dengan kebalikannya, tanpa kasus khusus.

Waktunya adalah O(n), dan salinan serta kebalikannya membutuhkan memori tambahan sebesar O(n).

Algoritma

Buat cleaned sebagai string kosong.
Untuk setiap karakter dalam s, jika karakter tersebut berupa huruf atau angka, tambahkan dalam huruf kecil.
Balik urutan cleaned.
Kembalikan apakah cleaned sama dengan kebalikannya.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Dua pointer yang melewati tanda baca

Intuisi

Salinan yang sudah dibersihkan hanya digunakan untuk membandingkan karakter yang berpasangan, dan kamu bisa langsung membandingkannya pada s. Geser setiap penunjuk melewati tanda baca, lalu bandingkan kedua karakter dalam huruf kecil. Penunjuk selalu berhenti pada karakter berikutnya yang dipertahankan dari masing-masing ujung, sehingga penunjuk mengunjungi pasangan (karakter pertama yang dipertahankan, karakter terakhir yang dipertahankan), (karakter kedua yang dipertahankan, karakter kedua dari belakang yang dipertahankan), dan seterusnya: tepat pasangan yang diperiksa oleh perbandingan terbalik.

Setiap langkah menggeser setidaknya satu penunjuk, jadi perulangan berjalan paling banyak n kali, dan hanya dua indeks yang disimpan. Perulangan juga berhenti saat menemukan ketidakcocokan pertama: Abc-dcbX menghasilkan false setelah membandingkan A dengan X.

Algoritma

Tetapkan left = 0 dan right = n-1.
Selama left < right: jika s[left] bukan huruf atau angka, tambah left lalu lanjutkan.
Jika tidak, jika s[right] bukan huruf atau angka, kurangi right lalu lanjutkan.
Jika tidak, bandingkan kedua karakter dalam huruf kecil. Jika keduanya berbeda, kembalikan false; jika sama, geser kedua penunjuk ke arah dalam.
Saat kedua penunjuk bertemu, kembalikan true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Jebakan dan kasus tepi

Membandingkan s[i] dengan s[n-1-i] pada string mentah. a-ba adalah palindrom setelah tanda hubung dihapus, tetapi karakter cermin dari - pada indeks 1 adalah b pada indeks 2.
Menggerakkan kedua penunjuk saat hanya salah satunya berada pada tanda baca. Lewati satu sisi saja setiap kali, atau kedua sisi akan bergeser tidak seirama.
Melewati tanda baca dalam perulangan bagian dalam tanpa pemeriksaan left < right. Pada ?!-_, proses akan melewati ujung string.
Menganggap digit sebagai karakter yang bisa diabaikan. 0P bernilai false: 0 tetap dipertahankan, dan itu bukan huruf p.
Di PHP dan R, string digit seperti 12321 bisa diterima sebagai angka. Ubah menjadi string terlebih dahulu.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Valid Palindrome?

Kedua pendekatan berjalan dalam waktu O(n), karena setiap karakter diperiksa sejumlah kali yang konstan. Membersihkan terlebih dahulu menggunakan memori tambahan O(n) untuk salinannya. Versi dua pointer menggunakan memori tambahan O(1), karena hanya menyimpan dua indeks.

Apakah string kosong merupakan palindrome?

Ya. Teks kosong terbaca sama dari kedua arah, jadi string seperti ?!-_, yang semua karakternya diabaikan, mengembalikan true. Kedua pendekatan mendapatkan hasil ini tanpa kode tambahan: teks yang sudah dibersihkan sama dengan kebalikannya yang kosong, dan kedua pointer tidak pernah menemukan pasangan yang berbeda.

Mengapa menggunakan dua pointer alih-alih membalik string?

Membalik membutuhkan salinan yang sudah dibersihkan dan salinan yang dibalik, sehingga memerlukan memori tambahan O(n). Dua pointer membandingkan pasangan yang sama secara langsung, lalu berhenti saat menemukan ketidakcocokan pertama, sering kali hanya setelah beberapa langkah.

def isPalindrome(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "Was_it_a_car_or_a_cat_I_saw?"

Output yang diharapkan

true