Palindrome String

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

İlk karakteri son karakterle, ikinci karakteri sondan ikinci karakterle ve bu şekilde ortaya doğru karşılaştırın. Herhangi bir çift farklıysa dize palindrom değildir; tüm çiftler eşleşiyorsa palindromdur. Her iki uçtan başlayıp içe doğru ilerleyen iki indeks bunu tek geçişte yapar.

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

Evet. İki işaretçi kontrolü, karakterleri yerinde okur ve yalnızca iki dizin saklar; bu nedenle O(1) ek alan kullanır. s dizgesini tersiyle karşılaştırmak yazması daha kısa olsa da n karakterden oluşan ikinci bir dizge oluşturur.

Q: Palindrom bir dizenin zaman karmaşıklığı nedir?

Uzunluğu n olan bir dize için O(n) olur. İki işaretçi kontrolü en fazla n / 2 karşılaştırma yapar ve ilk uyuşmazlıkta durur; bu nedenle ilk ve son karakterleri farklı olan bir dize tek karşılaştırmadan sonra belirlenir.

Q: Tek bir karakter palindrom mudur?

Evet. Tek karakter her iki yönde de aynı okunur, bu nedenle yanıt true olur. İki işaretçili döngüde left ve right ikisi de 0 dizininde 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 metin, soldan sağa ve sağdan sola aynı şekilde okunduğunda (örneğin level) palindromdur. Küçük İngilizce harflerden oluşan bir s metni 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ı okunduğunda 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 eşi yoktur ve gerek de yoktur; bu yüzden yanıt true.

Girdi: s = "abba"
Çıktı: true
Açıklama: Çift uzunlukta her harfin bir eşi vardır: iki a eşleşir ve iki b eşleşir, bu nedenle 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.

Gönderirken +16 gizli test

Ek soru

Harf büyüklüğü, boşluklar ve noktalama işaretleri yok sayıldığında Was it a car or a cat I saw gibi bir cümle palindromdur. Bu karakterleri atlamak için iki işaretçiyi nasıl değiştirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir palindrom, tersten yazılışıyla aynıdır; bu nedenle doğrudan kontrol, tersten yazılmış biçimini oluşturup karşılaştırır. Daha iyi kontrol hiçbir şey oluşturmaz: ilk karakter son karakterle, ikinci karakter sondan ikinci karakterle eşleşmeli ve bu şekilde ortaya doğru ilerlemelidir. İçe doğru ilerleyen iki indeks, bu çiftleri yerinde sınar ve ilk uyuşmazlıkta durur.

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

Sezgi

s değerini her iki yönde de aynı okumak, s değerinin tersinin kendisine eşit olduğu anlamına gelir. Bu yüzden tersini alıp karşılaştırın: racecar ters çevrildiğinde racecar olur ve coddy ters çevrildiğinde yddoc olur; bu ikisi farklıdır.

Tersini oluşturup karşılaştırmak her karaktere bir kez dokunur, dolayısıyla zaman karmaşıklığı O(n) olur. Ters kopya fazladan n karakter tutar; bu da O(n) ek alan demektir: n = 5 × 10^4 olduğunda, yalnızca karşılaştırılıp atılacak 50.000 karakter oluşturulur.

Ayrıca her seferinde tüm işlemi yapar. coddy ilk ve son harflerine bakılarak belirlenebilir; ancak bu yaklaşım, bakmadan önce beş harfin tamamını ters çevirir.

Algoritma

Dilin ters çevirme işlevini kullanarak veya son karakterden ilk karaktere doğru bir döngüyle s dizgesinin tersini oluştur.
Tersini s ile karşılaştır.
Eşitlerse true, değilse false döndür.

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

İki uçtan iki işaretçi

Sezgi

Tersine çevirme, i indeksindeki karakteri n-1-i indeksine taşır; bu nedenle s, ancak her i için s[i] değeri s[n-1-i] değerine eşitse tersine çevrilmiş hâline eşittir. Bu listedeki her çift iki kez görünür, bu yüzden yalnızca sol yarıyı kontrol edin. left değerini 0 indeksine, right değerini n-1 indeksine koyun, iki karakteri karşılaştırın ve her iki işaretçiyi de bir adım içeri doğru hareket ettirin.

İşaretçiler buluştuğunda veya birbirini geçtiğinde durun. racecar içinde (0, 6), (1, 5) ve (2, 4) indeks çiftlerini kontrol ederler, ardından eşleşmesi gerekmeyen orta e karakterinin bulunduğu 3 indeksinde buluşurlar. abba içinde (0, 3) ve (1, 2) çiftlerini kontrol ederler, ardından birbirlerini geçerler. Farklı olan ilk çift, yanıtın false olduğunu kanıtlar; bu yüzden hemen dönersiniz: coddy için sonuç tek bir karşılaştırmadan sonra belirlenir.

En fazla n / 2 karşılaştırma yapılır; bu da O(n) zaman demektir ve kullanılan tek bellek iki indekstir: O(1) alan. R bir istisnadır: önce dizeyi karakter kodlarından oluşan bir vektör olarak okur; bu işlem O(n) maliyetlidir.

Algoritma

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

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

Döngü kısa olduğu için hatalar sınırlarında ve dönüş ifadelerinde gizlidir.

Bir çift eşleşir eşleşmez true döndürmek. abca dış çift kontrolünü geçer ve iç çiftte başarısız olur; bu nedenle true yalnızca döngü bittikten sonra döndürülebilir.
right değerini n-1 yerine n olarak başlatmak; bu, dizenin sonrasını okur (C'de sonlandırıcı '\0'). Lua ve R'de dizinler 1 ile n arasında olduğundan, bu dillerde right değeri n olarak başlar.
Dizeleri adreslerine göre karşılaştırmak. C'de reversed == s, iki işaretçiyi karşılaştırır ve yeni oluşturulmuş bir kopya için her zaman false sonucunu verir; strcmp kullan.
Döngüde ters çevrilmiş diziyi result = result + ch ile oluşturmak. Her adım, o ana kadarki dizenin tamamını kopyalar; 50.000 harf için yaklaşık 1.25 × 10^9 karakter kopyası gerekir.
Swift dizgesini bir tamsayıyla indekslemek. Bu kod derlenmez; s.utf8 üzerinde kendi dizinleriyle ilerle veya karakterleri bir diziye kopyala.

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 bu şekilde ortaya doğru karşılaştırın. Herhangi bir çift farklıysa dize palindrom değildir; tüm çiftler eşleşiyorsa palindromdur. Her iki uçtan başlayıp içe doğru ilerleyen iki indeks bunu tek geçişte yapar.

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

Evet. İki işaretçi kontrolü, karakterleri yerinde okur ve yalnızca iki dizin saklar; bu nedenle O(1) ek alan kullanır. s dizgesini tersiyle karşılaştırmak yazması daha kısa olsa da n karakterden oluşan ikinci bir dizge oluşturur.

Palindrom bir dizenin zaman karmaşıklığı nedir?

Uzunluğu n olan bir dize için O(n) olur. İki işaretçi kontrolü en fazla n / 2 karşılaştırma yapar ve ilk uyuşmazlıkta durur; bu nedenle ilk ve son karakterleri farklı olan bir dize tek karşılaştırmadan sonra belirlenir.

Tek bir karakter palindrom mudur?

Evet. Tek karakter her iki yönde de aynı okunur, bu nedenle yanıt true olur. İki işaretçili döngüde left ve right ikisi de 0 dizininde başlar; döngü hiç çalışmaz ve işlev true döndürür.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "racecar"

Beklenen

true