Komşu çiftleri sil
Görev tanımı
Problem
Bir metin parçası verildiğinde, özdeş komşu iki karakteri tekrar tekrar sil. Bir çifti silmek çevresindeki karakterleri birbirine yaklaştırır; bu da silinecek yeni bir komşu çift oluşturabilir. Böyle bir çift kalmayana kadar devam et ve kalanı döndür.
Örnekler
Input: text = "abbaca"
Output: "ca"
Neden: bb'yi silmek aaca bırakır, aa'yı silmek de ca bırakır
Input: text = "azxxzy"
Output: "ay"
Neden: xx'i silmek zz oluşturur, o da silinir
Input: text = "aa"
Output: ""
Neden: edge case: her şey birbirini götürür ve hiçbir şey kalmaz
İpuçları
0 / 3
Her silmeden sonra bütün metni yeniden taramak doğrudur ama yavaştır. Bir silmenin yalnız boşluğun hemen etrafındaki karakterleri etkileyebileceğine dikkat et.
Sonucu soldan sağa kur ve son karakterine bakmaya devam et. Tek ucuz işlemleri sona ekleme ve sondan çıkarma olan bir yapı buna tam olarak uyar.
Karakterleri bir stack'e birer birer push et. Push etmeden önce gelen karakteri tepedekiyle karşılaştır: eşleşiyorlarsa push etmek yerine pop et; bu, götürmeyi yapar ve altındaki bir sonraki adayı hemen ortaya çıkarır. Sonda kalan stack'i birleştir.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
Bir stack cevabın şimdiye kadar kurulan kısmını tutar ve tepesi her zaman yeni gelenin yanına oturacağı karakterdir. Bu yüzden bir eşleşme push etmek yerine pop ederek götürür; bu da altındaki karakteri yeni komşu olarak ortaya çıkarır, böylece götürme zincirleri yeniden tarama olmadan kendiliğinden olur. Her karakter en fazla bir kez push ve pop edilir. Zaman O(n), stack için alan O(n).
def collapse_pairs(text):
stack = []
for ch in text:
if stack and stack[-1] == ch:
stack.pop() # the pair annihilates, exposing the one below
else:
stack.append(ch)
return "".join(stack)
print(collapse_pairs("abbaca")) # -> ca
print(collapse_pairs("azxxzy")) # -> ay
print(collapse_pairs("aa")) # ->Kodda değil de fikirde mi takıldın? Geçerli parantezler bunu anlatıyor.