Valid Palindrome

Q: Valid Palindrome algoritmasının zaman karmaşıklığı nedir?

Her iki yaklaşım da O(n) zamanda çalışır; çünkü her karaktere sabit sayıda kez bakılır. Önce temizleme, kopya için O(n) ek bellek kullanır. İki işaretçili sürüm, yalnızca iki dizin tuttuğu için O(1) ek bellek kullanır.

Q: Alfasayısal olmayan karakterleri yok sayarak bir palindromu nasıl kontrol edersiniz?

Dizenin her iki ucunda birer işaretçi tutun. Bir işaretçiyi harf veya rakam olmayan her karakterin üzerinden ilerletin ve her iki işaretçi de harf veya rakamların üzerinde olduğunda bunları küçük harfe çevirerek karşılaştırın. İşaretçiler buluşana kadar karşılaştırılan her çift eşleşirse dize bir palindromdur.

Q: Boş bir dizge palindrom mudur?

Evet. Boş bir metin her iki yönde de aynı okunur; bu nedenle tüm karakterleri yok sayılan ?!-_ gibi bir dize true döndürür. Her iki yaklaşım da bunu ek kod olmadan sağlar: temizlenmiş metin, ters çevrilmiş boş hâline eşittir ve iki işaretçi hiçbir zaman farklı bir çift bulmaz.

Q: Neden dizgeyi ters çevirmek yerine iki işaretçi kullanmalıyız?

Tersine çevirme, temizlenmiş bir kopya ve ters çevrilmiş bir kopya gerektirir; bu da O(n) ek bellek demektir. İki işaretçi aynı çiftleri yerinde karşılaştırır ve ilk uyuşmazlıkta, çoğu zaman birkaç adım sonra durabilir. Görüşmeciler genellikle devam sorusu olarak bu sürümü ister.

Kolayİki işaretçi

+10

Sana s dizgesi verilir. Yalnızca harflerini ve rakamlarını tut, büyük ve küçük harfleri aynı harf olarak değerlendir ve geriye kalanın soldan sağa okunuşuyla sağdan sola okunuşunun aynı olup olmadığına karar ver. Aynıysa true, değilse false döndür.

., !, ?, :, ;, - veya _ gibi diğer tüm karakterler yok sayılır. s içinde hiç harf veya rakam yoksa geriye hiçbir şey kalmaz ve boş bir metin palindrom sayılır.

Fonksiyon

isPalindrome(s: string) → boolean

sstring: kontrol edilecek metin, noktalama işaretleri dahil
Döndürürboolean: s içindeki harfler ve rakamlar, büyük/küçük harf ayrımı göz ardı edildiğinde her iki yönde de aynı okunuyorsa true

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s İngilizce harfler, rakamlar ve . ! ? : ; - _ noktalama işaretlerini içerir; boşluk içermez.

Örnekler

Girdi: s = "Was_it_a_car_or_a_cat_I_saw?"
Çıktı: true
Açıklama: Alt çizgileri ve soru işaretini kaldırıp büyük harfleri küçültün: wasitacaroracatisaw elde edersiniz; bu, tersten de aynıdır.

Girdi: s = "race-a-car"
Çıktı: false
Açıklama: Tireler olmadan metin raceacar olur. Sağdan okunduğunda race yerine raca ile başlar: ortadaki e harfinin ayna eşi a olduğundan cevap false olur.

Girdi: s = "Step-on-no-pets!"
Çıktı: true
Açıklama: Korunan metin steponnopets. Büyük harfli S, büyük/küçük harf ayrımı yok sayıldığı için sondaki s ile eşleşir; tirelerin ve ! işaretinin ise hiçbir etkisi yoktur.

Gönderirken +25 gizli test

Ek soru

Temizlenmiş bir s kopyası oluşturmadan, bunu O(1) ek bellekle çözebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Palindrom kontrolünün kendisi bildiktir: tutulan ilk karakter son karaktere, ikinci karakter sondan ikinci karaktere eşit olmalıdır ve bu böyle devam eder. Bu sürümü zorlaştıran şey, karşılaştırdığınız karakterlerin s dizgesinde birbirinin ayna görüntüsü olan indekslerde bulunmamasıdır; çünkü noktalama işaretleri iki yana eşit olmayan biçimde dağılmıştır. Önce bu işaretleri kaldırabilir ya da iki işaretçinin birbirine doğru ilerlerken bu işaretleri atlamasını sağlayabilirsiniz.

Dizgiyi temizleyin, ardından tersiyle karşılaştırın

Sezgi

Problemin gerçekten sorduğu metni oluştur. s üzerinde ilerle; her harfi veya rakamı küçük harfe çevir ve diğer her şeyi atla. Step-on-no-pets! için sonuç steponnopets olur. Şimdi soru, basit palindrom sorusudur: Bu metin kendi tersine çevrilmiş hâline eşit mi?

Bu doğrudur; çünkü temizleme işlemi, problemin yok saymamızı söylediği karakterleri kaldırır ve yok saymamızı söylediği harf büyüklüğü farkını ortadan kaldırır. s hiçbir harf veya rakam içermiyorsa temizlenmiş metin boş olur ve boş bir metin kendi tersine çevrilmiş hâline eşittir; dolayısıyla özel bir durum olmadan yanıt true olur.

Her karakter, temizleme için bir kez ve karşılaştırma için bir kez daha okunur; bu nedenle zaman karmaşıklığı O(n) olur. Temizlenmiş kopya ve bunun tersine çevrilmiş hâli O(n) ek bellek kullanır; sonraki yaklaşım bu maliyeti ortadan kaldırır.

Algoritma

Boş bir metin cleaned oluşturun.
s içindeki her karakter için, harf veya rakamsa küçük harfe çevirip ekleyin.
cleaned metnini ters çevirin.
cleaned metninin tersiyle eşit olup olmadığını döndürün.

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

Noktalama işaretlerini atlayan iki işaretçi

Sezgi

Temizlenmiş kopya yalnızca eşleşen karakterleri karşılaştırabilmen için var. Aynı karşılaştırmayı doğrudan s üzerinde de yapabilirsin. left değerini ilk indekse, right değerini son indekse koy. Her adımda, left noktalama işaretini gösteriyorsa sağa ilerlet; right noktalama işaretini gösteriyorsa sola ilerlet. İkisi de harf veya rakam gösterdiğinde, küçük harfe çevirip karşılaştır. Eşleşmeme durumu false anlamına gelir; eşleşme durumunda her iki işaretçi de içeri doğru bir adım ilerler.

Bu neden aynı kontrolü yapar? İşaretçiler her zaman her iki uçtan bir sonraki korunan karakterde durur. Bu nedenle şu çiftleri ziyaret ederler: (korunan ilk karakter, korunan son karakter), (korunan ikinci karakter, sondan ikinci korunan karakter) ve bu şekilde devam ederler. Bunlar, tersine çevirip yapılan karşılaştırmanın incelediği çiftlerin aynısıdır. Abc-dcbX içinde ilk çift A ve X karakterlerinden oluşur ve tek bir karşılaştırmadan sonra sonuç false olur.

Her adımda en az bir işaretçi ilerler ve işaretçiler buluştuklarında dururlar; bu nedenle döngü en fazla n kez çalışır. İki indeks dışında hiçbir şey saklanmadığından, ek bellek kullanımı O(1) olur.

Algoritma

left = 0 ve right = n-1 olarak ayarla.
left < right iken: s[left] bir harf veya rakam değilse left değerini artır ve devam et.
Aksi takdirde, s[right] bir harf veya rakam değilse right değerini azalt ve devam et.
Aksi takdirde, iki karakteri küçük harfe dönüştürerek karşılaştır. Farklılarsa false döndür; eşleşiyorlarsa her iki işaretçiyi de içeri doğru ilerlet.
İşaretçiler buluştuğunda true döndür.

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

Tuzaklar ve uç durumlar

Hataların çoğu atlanan karakterlerden ve büyük-küçük harf kullanımından kaynaklanır.

Ham dizgede s[i] ile s[n-1-i] değerlerini karşılaştırmak. Tire kaldırıldığında a-ba bir palindromdur, ancak - karakterinin 1. indeksteki ham yansıması, 2. indeksteki b karakteridir.
İşaretçilerden yalnızca biri noktalama işaretinin üzerindeyken ikisini birden ilerletmek. Her seferinde yalnızca bir taraftaki karakteri atla; aksi hâlde iki tarafın adımları şaşar.
Diğer işaretçiyi geçen bir iç döngüde noktalama işaretlerini atlamak. ?!-_ için sınırlandırılmamış bir iç döngü dizgenin sonunu aşar; her harekette left < right kontrolünü yap.
Rakamları önemsiz karakterler olarak değerlendirmek. 0P, false değeridir: 0 rakamı korunur ve karşılaştırılır; bu rakam p harfi değildir.
Hiçbir karakter kalmadığında false döndürmek. Yalnızca noktalama işaretlerinden oluşan, örneğin . gibi bir dizgenin temizlenmiş metni boştur ve bu bir palindromdur.
Yalnızca rakamlardan oluşan 12321 gibi bir dizge, PHP ve R'ye sayı olarak ulaşabilir. Önce onu bir dizgeye dönüştür.

Sıkça sorulan sorular4

Valid Palindrome algoritmasının zaman karmaşıklığı nedir?

Her iki yaklaşım da O(n) zamanda çalışır; çünkü her karaktere sabit sayıda kez bakılır. Önce temizleme, kopya için O(n) ek bellek kullanır. İki işaretçili sürüm, yalnızca iki dizin tuttuğu için O(1) ek bellek kullanır.

Alfasayısal olmayan karakterleri yok sayarak bir palindromu nasıl kontrol edersiniz?

Dizenin her iki ucunda birer işaretçi tutun. Bir işaretçiyi harf veya rakam olmayan her karakterin üzerinden ilerletin ve her iki işaretçi de harf veya rakamların üzerinde olduğunda bunları küçük harfe çevirerek karşılaştırın. İşaretçiler buluşana kadar karşılaştırılan her çift eşleşirse dize bir palindromdur.

Boş bir dizge palindrom mudur?

Evet. Boş bir metin her iki yönde de aynı okunur; bu nedenle tüm karakterleri yok sayılan ?!-_ gibi bir dize true döndürür. Her iki yaklaşım da bunu ek kod olmadan sağlar: temizlenmiş metin, ters çevrilmiş boş hâline eşittir ve iki işaretçi hiçbir zaman farklı bir çift bulmaz.

Neden dizgeyi ters çevirmek yerine iki işaretçi kullanmalıyız?

Tersine çevirme, temizlenmiş bir kopya ve ters çevrilmiş bir kopya gerektirir; bu da O(n) ek bellek demektir. İki işaretçi aynı çiftleri yerinde karşılaştırır ve ilk uyuşmazlıkta, çoğu zaman birkaç adım sonra durabilir. Görüşmeciler genellikle devam sorusu olarak bu sürümü ister.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "Was_it_a_car_or_a_cat_I_saw?"

Beklenen

true