Bir silmeden sonra palindrom
Görev tanımı
Problem
Bir kelime oyunu, düz ve tersten aynı okunan bir string'i kabul ediyor ve tek bir yazım hatasını affediyor. Küçük harflerden oluşan bir s string'i verildiğinde, s zaten bir palindromsa ya da tam olarak bir karakter silindikten sonra palindrom oluyorsa True, değilse False döndür. Boş string palindrom sayılır.
Örnekler
Input: s = "racexcar"
Output: True
Neden: x'i silmek "racecar" bırakır
Input: s = "abcda"
Output: False
Neden: dıştaki a'lar eşleştikten sonra b ve d anlaşmıyor, ikisinden birini atmak da yine başarısız
Input: s = ""
Output: True
Neden: edge case: karşılaştırılacak bir şey yok, yani silmeye gerek yok
İpuçları
0 / 3
Olası her silmeyi deneyip her sonucu kontrol etmek karesel. String'in çoğu ikinci bir bakışa hiç ihtiyaç duymaz.
İki uçtan içe doğru iki pointer dolaştır. Karakterler eşleştiği sürece hiçbir karar gerekmez. Tek ilginç an ilk uyuşmazlık.
İlk uyuşmazlıkta silinen karakter pointer'ların altındaki ikisinden biri olmalı. İç parçanın soldaki olmadan ya da sağdaki olmadan kendi başına palindrom olup olmadığını kontrol et. Pointer'lar uyuşmazlık olmadan buluşursa cevap zaten evet.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- s holds lowercase letters
- the empty string counts as a palindrome
Çözüm
Eşleşen dış karakterler asla sorun olamaz; bu yüzden iki pointer tek silme hakkını harcamadan onları atlar. İlk uyuşmazlıkta herhangi bir düzeltme o iki karakterden birini silmelidir, çünkü onların dışındaki her karakterin zaten eşi vardır. Bu, her biri düz bir palindrom taramasıyla kontrol edilen tam olarak iki aday substring bırakır ve onların içinde başka seçim çıkmaz. Her karakter en fazla birkaç kez karşılaştırıldığı için zaman O(n), alan O(1).
def almost_palindrome(s):
def is_pal(i, j): # plain two-pointer check of s[i..j]
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# the one deletion must remove s[i] or s[j]
return is_pal(i + 1, j) or is_pal(i, j - 1)
i, j = i + 1, j - 1
return True
print(almost_palindrome("racexcar")) # -> True
print(almost_palindrome("abcda")) # -> False
print(almost_palindrome("")) # -> TrueKodda değil de fikirde mi takıldın? Geçerli palindrom bunu anlatıyor.