İçeriğe geç

Geçerli palindrom

Ders 2 / 11 · 4 dk

Geçerli palindrom

Adım 1/7

Palindrom iki yönden de aynı okunur, o yüzden onu iki uçtan aynı anda oku; ters kopyaya gerek yok.

Fikir

Palindrom iki uçtan da aynı okunur; o halde iki uçtan kontrol et. Başa bir pointer (işaretçi), sona bir tane daha koy ve ikisini birbirine doğru ilerlet.

Tek bir uyuşmazlık kesin hayır demek. Ortada buluşmak kesin evet — ters çevrilmiş kopya yok, ek bellek yok.

Gerçek hayattan örnek

Barkod ve hesap numarası kontrolcüleri de aynı biçimde test yapar: baştan ve sondan aynı anda okur, iki taraf uyuşmadığı anda bırakır. Önce tüm kodu tarayıp sonra karşılaştırmak, sonucu zaten belli olan yarıyı boşuna yapmak demek.

Kod

Sıra sende

Boşluğu doldur.

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

print(is_palindrome("abba"), is_palindrome("abca"))   # want True False

Mini quiz

1 / 3

İki pointer (two pointers) ile palindrom kontrolünün maliyeti nedir?