Noktalamayı yok sayan palindrom kontrolü
Görev tanımı
Problem
Büyük-küçük harfi yok sayıp harf ya da rakam olmayan her karakteri atladığında bir string'in düz ve tersten aynı okunup okunmadığına karar ver. Önce iki ucu karşılaştırıp aralarındakinin üzerinde özyineleyen özyinelemeli bir fonksiyon olarak yaz, sonra onu her uzunluktaki string'i işleyen bir döngüye çevir.
Örnekler
Input: s = "A man, a plan, a canal: Panama"
Output: True
Neden: yalnız harfler iki yönde de amanaplanacanalpanama okunuyor
Input: s = "race a car"
Output: False
Neden: raceacar ters çevrilince racaecar oluyor
Input: s = ".,!"
Output: True
Neden: edge case: noktalama atlanınca hiçbir şey kalmıyor, boş string de bir palindromdur
İpuçları
0 / 3
En dıştaki karakter çiftine bak. Biri noktalamaysa onu at ve aynı soruyu yeniden sor. İkisi de sayılıyorsa ve farklıysa cevap hayır.
Her çağrı O(1) olsun diye dilimlemek yerine soldan bir i, sağdan bir j olmak üzere iki indeks geçir. Temel durum i >= j.
Her özyinelemeli çağrı, sonucu değiştirilmeden döndürülen, fonksiyonun yaptığı son şeydir; yani bir tail call. Python yine de her çerçeveyi tutar; bu yüzden onu, çağrıların olduğu yerde i ve j'yi güncelleyen bir while döngüsü olarak yeniden yaz.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Özyinelemeli versiyon tanımı doğrudan ifade eder: alfanümerik olmayan bir ucu atla, eşleşmeyen bir çiftte başarısız ol, aksi halde iki ucu da içe kaydır. Her özyinelemeli çağrı tail konumundadır, çünkü sonucu değiştirilmeden ve sonrasında hiçbir iş kalmadan döndürülür; bu yüzden çağrıyı yapan çerçeve ölü yüktür. Python bu çerçeveleri yeniden kullanmaz; bu yüzden mantık doğru olsa bile birkaç bin karakterlik bir string özyineleme (recursion) sınırını taşırır. Döngü mekanik çeviridir: i ve j parametreleri değişken olur, her tail call da onların bir güncellemesi ve ardından döngüde bir tur daha olur. İkisi de O(n) zamanda çalışır; özyinelemeli olan O(n) stack, döngü O(1) kullanır.
def is_palindrome(s, i=0, j=None):
if j is None:
j = len(s) - 1
if i >= j:
return True
if not s[i].isalnum():
return is_palindrome(s, i + 1, j)
if not s[j].isalnum():
return is_palindrome(s, i, j - 1)
if s[i].lower() != s[j].lower():
return False
return is_palindrome(s, i + 1, j - 1) # tail call: nothing happens after it
def is_palindrome_loop(s):
i, j = 0, len(s) - 1
while i < j: # each tail call becomes one update
if not s[i].isalnum():
i += 1
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False
else:
i, j = i + 1, j - 1
return True
print(is_palindrome("A man, a plan, a canal: Panama")) # -> True
print(is_palindrome("race a car")) # -> False
print(is_palindrome(".,!")) # -> True
print(is_palindrome_loop("ab" * 50000 + "a")) # -> TrueKodda değil de fikirde mi takıldın? Tail call'lar ve döngüler bunu anlatıyor.