Palindrome String

Q: Bir dizenin palindrom olup olmadığını nasıl kontrol edersiniz?

İlk karakteri son karakterle, ikinci karakteri sondan ikinci karakterle ve böylece ortaya doğru karşılaştır. Herhangi bir çift farklıysa dizge palindrom değildir. Her iki uçtan başlayıp ortaya doğru ilerleyen iki indeks bunu tek geçişte yapar.

Q: Ek bellek kullanmadan bir palindrom olup olmadığını kontrol edebilir misin?

Evet. İki işaretçili kontrol, karakterleri yerinde okur ve iki dizin saklar; bu nedenle O(1) ek alan kullanır. s dizgesini ters çevrilmiş hâliyle karşılaştırmak daha kısa yazılır, ancak n karakterden oluşan ikinci bir dizge oluşturur.

Q: Palindrom bir dizgeyi kontrol etmenin zaman karmaşıklığı nedir?

Uzunluğu n olan bir dizge için O(n) . İki işaretçi kontrolü en fazla n / 2 karşılaştırma yapar ve ilk uyuşmazlıkta durur; bu nedenle coddy bir karşılaştırma yapar.

Q: Tek bir karakter palindrom mudur?

Evet, her iki yönde de aynı okunur. İki işaretçili döngüde left ve right ikisi de 0 indeksinde başlar, döngü hiç çalışmaz ve işlev true döndürür.

Başlangıçİki işaretçi Diziler ve dizgiler

+10

Bir dize, soldan sağa ve sağdan sola aynı şekilde okunduğunda (örneğin level) palindrom olur. Küçük İngilizce harflerden oluşan bir s dizesi alan ve s bir palindromsa true, değilse false döndüren bir fonksiyon yaz.

Fonksiyon

isPalindrome(s: string) → boolean

sstring: kontrol edilecek küçük harfli dize
Döndürürboolean: s her iki yönde de aynı okunuyorsa doğru

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca küçük İngilizce harfler (a ile z arası) içerir.

Örnekler

Girdi: s = "racecar"
Çıktı: true
Açıklama: Dıştan içe doğru karşılaştır: r ile r, a ile a, c ile c. Ortadaki e'nin bir eşi yok ve eşe ihtiyacı da yok, bu yüzden yanıt true.

Girdi: s = "abba"
Çıktı: true
Açıklama: Uzunluk çift olduğunda her harfin bir eşi vardır: iki a eşleşir ve iki b eşleşir, dolayısıyla yanıt true olur.

Girdi: s = "coddy"
Çıktı: false
Açıklama: İlk harf c ve son harf y zaten farklıdır, bu yüzden coddy bir palindrom değildir ve cevap false olur.

Ek soru

Boşlukları ve noktalama işaretlerini atlayıp büyük/küçük harf farkını göz ardı etmek için iki işaretçiyi nasıl değiştirirdin; böylece Was it a car or a cat I saw bir palindrom olarak sayılır?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Palindrom, tersten yazılışıyla aynıdır; bu yüzden tersten yazılmış hâlini oluşturup karşılaştırabilirsin. Kopyaya gerek yoktur: ilk karakter son karakterle, ikinci karakter sondan ikinci karakterle eşleşmelidir ve bu böyle devam eder. İçeri doğru ilerleyen iki indeks, bu karakter çiftlerini yerinde test eder ve ilk uyuşmazlıkta durur.

Ters çevrilmiş hâliyle dizeyi karşılaştırın

Sezgi

s dizgesini ters çevirip karşılaştır: racecar ters çevrildiğinde racecar olur ve coddy ters çevrildiğinde yddoc olur. Bir dizge, yalnızca tersiyle eşitse her iki yönde de aynı okunur.

Zaman karmaşıklığı O(n)’dir, ancak ters çevrilmiş kopya O(n) ek alan gerektirir; n = 5 × 10^4 iken 50.000 karakter. İşlem ayrıca her zaman dizgenin tamamını işler: coddy için karar ilk ve son harflerinden verilebilir, ancak önce beş harfin tümü ters çevrilir.

Algoritma

s'nin tersini, dilin tersine çevirme işlevini kullanarak veya son karakterden ilk karaktere doğru ilerleyen bir döngüyle oluştur.
Tersini s ile karşılaştır.
Eşitlerse true, aksi takdirde false döndür.

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

Her iki uçtan iki işaretçi

Sezgi

Ters çevirme, i indeksini n-1-i indeksine taşır; bu nedenle s, yalnızca her i için s[i], s[n-1-i] değerine eşitse tersiyle tam olarak aynı olur. Bu koşulda her çift iki kez geçtiğinden, sol yarıyı kontrol etmek yeterlidir. racecar dizgesindeki çiftler (0, 6), (1, 5) ve (2, 4) şeklindedir; 3. indeksteki ortadaki e için eş gerekmez.

Farklı olan ilk çift, yanıtın false olduğunu kanıtlar; bu nedenle coddy için sonuca tek karşılaştırmadan sonra ulaşılır. En fazla n / 2 karşılaştırma yapılır; zaman karmaşıklığı O(n), iki indeks için alan karmaşıklığı O(1)'dir. R, dizgeyi önce karakter kodlarından oluşan bir vektör olarak okur; bu işlem O(n) maliyetlidir.

Algoritma

left = 0 ve right = n-1 olarak ayarla.
left < right olduğu sürece s[left] ile s[right] değerlerini karşılaştır.
Farklılarsa false döndür.
Aksi takdirde left değerini 1 artır, right değerini 1 azalt ve tekrarla.
İşaretçiler buluştuğunda veya birbirlerini geçtiğinde, her eşleşme tamamlanmıştır: true döndür.

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

Tuzaklar ve uç durumlar

Bir çift eşleşir eşleşmez true döndürmek. abca dıştaki çifti geçer ve içteki çiftte başarısız olur; bu yüzden true ancak döngüden sonra gelir.
right değerini n-1 yerine n olarak başlatmak, dizinin sonrasını okumaya yol açar (C'de sonlandırıcı '\0'). Lua ve R'de indisler 1'den n'e kadar gider; dolayısıyla bu dillerde right gerçekten n ile başlar.
C'de dizeleri == ile karşılaştırmak. reversed == s iki işaretçiyi karşılaştırır ve bir kopya için false sonucunu verir; strcmp kullanın.
Ters diziyi result = result + ch ile oluşturmak. Her adım o ana kadarki dizeyi kopyalar: 50.000 harf için yaklaşık 1.25 × 10^9 karakter kopyası.
Swift dizgesini bir tamsayıyla indekslemek: kod derlenmez. s.utf8 üzerinde ilerleyin veya karakterleri bir diziye kopyalayın.

Sıkça sorulan sorular4

Bir dizenin palindrom olup olmadığını nasıl kontrol edersiniz?

İlk karakteri son karakterle, ikinci karakteri sondan ikinci karakterle ve böylece ortaya doğru karşılaştır. Herhangi bir çift farklıysa dizge palindrom değildir. Her iki uçtan başlayıp ortaya doğru ilerleyen iki indeks bunu tek geçişte yapar.

Ek bellek kullanmadan bir palindrom olup olmadığını kontrol edebilir misin?

Evet. İki işaretçili kontrol, karakterleri yerinde okur ve iki dizin saklar; bu nedenle O(1) ek alan kullanır. s dizgesini ters çevrilmiş hâliyle karşılaştırmak daha kısa yazılır, ancak n karakterden oluşan ikinci bir dizge oluşturur.

Palindrom bir dizgeyi kontrol etmenin zaman karmaşıklığı nedir?

Uzunluğu n olan bir dizge için O(n). İki işaretçi kontrolü en fazla n / 2 karşılaştırma yapar ve ilk uyuşmazlıkta durur; bu nedenle coddy bir karşılaştırma yapar.

Tek bir karakter palindrom mudur?

Evet, her iki yönde de aynı okunur. İki işaretçili döngüde left ve right ikisi de 0 indeksinde başlar, döngü hiç çalışmaz ve işlev true döndürür.

def isPalindrome(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "racecar"

Beklenen Çıktı

true