Palindrome String

Q: Bagaimana cara memeriksa apakah sebuah string adalah palindrom?

Bandingkan karakter pertama dengan karakter terakhir, karakter kedua dengan karakter kedua dari belakang, dan seterusnya menuju tengah. Jika ada pasangan yang berbeda, string tersebut bukan palindrom. Dua indeks yang dimulai dari kedua ujung dan bergerak ke dalam melakukan ini dalam satu kali lintasan.

Q: Bisakah kamu memeriksa palindrome tanpa memori tambahan?

Ya. Pemeriksaan dengan dua pointer membaca karakter langsung dan menyimpan dua indeks, sehingga menggunakan ruang tambahan O(1) . Membandingkan s dengan kebalikannya lebih singkat ditulis, tetapi membuat string kedua dengan n karakter.

Q: Apa kompleksitas waktu untuk memeriksa string palindrom?

O(n) untuk string dengan panjang n . Pemeriksaan dua pointer melakukan paling banyak n / 2 perbandingan dan berhenti pada ketidakcocokan pertama, jadi coddy hanya membutuhkan satu perbandingan.

Q: Apakah satu karakter merupakan palindrom?

Ya, hasilnya sama saat dibaca dari kedua arah. Dalam for loop dua pointer, left dan right sama-sama dimulai dari indeks 0, perulangan tidak pernah berjalan, dan fungsi mengembalikan true .

PemulaTwo pointers Array dan string

+10

Sebuah string disebut palindrom jika dibaca sama dari kiri ke kanan maupun dari kanan ke kiri, seperti level. Tulis fungsi yang menerima string s yang terdiri dari huruf kecil bahasa Inggris dan mengembalikan true jika s adalah palindrom, dan false jika tidak.

Fungsi

isPalindrome(s: string) → boolean

sstring: string huruf kecil yang akan diperiksa
Mengembalikanboolean: benar jika s terbaca sama dari kedua arah

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf kecil bahasa Inggris (a sampai z).

Contoh

Input: s = "racecar"
Output: true
Penjelasan: Bandingkan dari bagian luar ke dalam: r dengan r, a dengan a, c dengan c. e di tengah tidak memiliki pasangan dan tidak membutuhkannya, jadi jawabannya adalah true.

Input: s = "abba"
Output: true
Penjelasan: Dengan panjang genap, setiap huruf memiliki pasangan: kedua a cocok dan kedua b cocok, jadi jawabannya adalah true.

Input: s = "coddy"
Output: false
Penjelasan: Huruf pertama c dan huruf terakhir y sudah berbeda, jadi coddy bukan palindrom dan jawabannya adalah false.

Pertanyaan lanjutan

Bagaimana kamu akan mengubah kedua pointer agar melewati spasi dan tanda baca serta mengabaikan huruf besar dan kecil, sehingga Was it a car or a cat I saw dianggap sebagai palindrome?

Petunjuk

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

0 dari 3 dibuka

Solusi

Palindrom sama dengan kebalikannya, jadi kamu bisa membuat versi terbaliknya lalu membandingkannya. Kamu tidak perlu membuat salinan: karakter pertama harus cocok dengan karakter terakhir, karakter kedua dengan karakter kedua dari belakang, dan seterusnya. Dua indeks yang bergerak ke dalam menguji pasangan tersebut langsung pada tempatnya dan berhenti saat menemukan ketidakcocokan pertama.

Bandingkan string dengan kebalikannya

Intuisi

Balikkan s lalu bandingkan: racecar jika dibalik menjadi racecar, dan coddy jika dibalik menjadi yddoc. Sebuah string dibaca sama dari kedua arah tepat ketika nilainya sama dengan kebalikannya.

Waktunya O(n), tetapi salinan yang dibalik membutuhkan ruang tambahan O(n), yaitu 50.000 karakter saat n = 5 × 10^4. Prosesnya juga selalu memeriksa seluruh string: hasil untuk coddy sudah bisa ditentukan dari huruf pertama dan terakhirnya, tetapi kelima hurufnya tetap dibalik terlebih dahulu.

Algoritma

Buat kebalikan dari s, dengan fungsi reverse dalam bahasa tersebut atau perulangan dari karakter terakhir hingga karakter pertama.
Bandingkan kebalikannya dengan s.
Kembalikan true jika keduanya sama dan false jika tidak.

def isPalindrome(s):
    return s == s[::-1]

Dua pointer dari kedua ujung

Intuisi

Membalik memindahkan indeks i ke indeks n-1-i, sehingga s sama persis dengan kebalikannya jika s[i] sama dengan s[n-1-i] untuk setiap i. Setiap pasangan muncul dua kali dalam kondisi itu, jadi cukup memeriksa separuh bagian kiri. Dalam racecar, pasangan tersebut adalah (0, 6), (1, 5), dan (2, 4); e di tengah pada indeks 3 tidak memerlukan pasangan.

Pasangan pertama yang berbeda membuktikan bahwa jawabannya adalah false, jadi hasil untuk coddy dapat ditentukan setelah satu perbandingan. Paling banyak ada n / 2 perbandingan, dengan waktu O(n), dan dua indeks menggunakan ruang O(1). R pertama-tama membaca string sebagai vector kode karakter, yang membutuhkan O(n).

Algoritma

Tetapkan left = 0 dan right = n-1.
Selama left < right, bandingkan s[left] dengan s[right].
Jika keduanya berbeda, kembalikan false.
Jika tidak, tambahkan 1 ke left, kurangi 1 dari right, lalu ulangi.
Saat kedua pointer bertemu atau saling melewati, setiap pasangan sudah cocok: kembalikan true.

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

Jebakan dan kasus tepi

Mengembalikan true segera setelah satu pasangan cocok. abca lolos pada pasangan luarnya dan gagal pada pasangan dalamnya, jadi true baru dikembalikan setelah perulangan.
Memulai right dari n, bukan n-1, sehingga pembacaan melewati akhir (dalam C, karakter terminasi '\0'). Dalam Lua dan R, indeks dimulai dari 1 hingga n, jadi di sana right memang dimulai dari n.
Membandingkan string dengan == dalam C. reversed == s membandingkan dua pointer dan hasilnya false untuk salinan, gunakan strcmp.
Membuat string terbalik dengan result = result + ch. Setiap langkah menyalin string sejauh itu, sekitar 1.25 × 10^9 salinan karakter untuk 50,000 huruf.
Mengindeks string Swift dengan bilangan bulat: kode ini tidak dapat dikompilasi. Telusuri s.utf8 atau salin karakter ke dalam array.

Pertanyaan yang sering diajukan4

Bagaimana cara memeriksa apakah sebuah string adalah palindrom?

Bandingkan karakter pertama dengan karakter terakhir, karakter kedua dengan karakter kedua dari belakang, dan seterusnya menuju tengah. Jika ada pasangan yang berbeda, string tersebut bukan palindrom. Dua indeks yang dimulai dari kedua ujung dan bergerak ke dalam melakukan ini dalam satu kali lintasan.

Bisakah kamu memeriksa palindrome tanpa memori tambahan?

Ya. Pemeriksaan dengan dua pointer membaca karakter langsung dan menyimpan dua indeks, sehingga menggunakan ruang tambahan O(1). Membandingkan s dengan kebalikannya lebih singkat ditulis, tetapi membuat string kedua dengan n karakter.

Apa kompleksitas waktu untuk memeriksa string palindrom?

O(n) untuk string dengan panjang n. Pemeriksaan dua pointer melakukan paling banyak n / 2 perbandingan dan berhenti pada ketidakcocokan pertama, jadi coddy hanya membutuhkan satu perbandingan.

Apakah satu karakter merupakan palindrom?

Ya, hasilnya sama saat dibaca dari kedua arah. Dalam for loop dua pointer, left dan right sama-sama dimulai dari indeks 0, perulangan tidak pernah berjalan, dan fungsi mengembalikan true.

def isPalindrome(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "racecar"

Output yang diharapkan

true