Dergiden fidye notu
Görev tanımı
Problem
Bir tabelacı yeni bir mesaj yazmak için yedek bir pankarttan harfler kesiyor. Küçük harfli iki string note ve banner verildiğinde, banner'ın her harfi en fazla bir kez kullanılarak note yazılabiliyorsa True döndür. İki string de en fazla 100.000 harf, bu yüzden note'un her harfi için banner'ı yeniden aramaktan kaçın.
Örnekler
Input: note = "aab", banner = "baa"
Output: True
Neden: banner'da iki a ve bir b var, note'un tam olarak ihtiyaç duyduğu kadar
Input: note = "aa", banner = "ab"
Output: False
Neden: note iki a istiyor, banner'da yalnız bir tane var
Input: note = "", banner = "xyz"
Output: True
Neden: edge case: boş bir note hiç harf gerektirmez
İpuçları
0 / 3
Burada sıra önemli değil, yalnız her harften kaç tane olduğu. Banner'ı hangi tek tablo özetler?
Banner'ın her harfini bir kez say. Sonra note'un her harfi o sayıdan bir çekiliştir.
Note'u dolaş ve harfinin sayısından bir çıkar. Bir sayı sıfırın altına düşecekse banner'da o harf bitmiştir, False döndür.
- Hedef zaman
- O(n + m)
- Hedef alan
- O(1)
Kısıtlar
- note and banner are lowercase letters
- each string has at most 10⁵ letters
Çözüm
Yalnız her harfin kopya sayısı önemli, bu yüzden banner tek geçişte bir harf sayıları tablosuna indirilir. Note'un her harfi sonra o tablodan bir kopya harcar; sayısı zaten sıfır olan ilk harf de note'un yazılamayacağını kanıtlar. İki string'in her harfine bir kez dokunulur; zaman O(n + m), tablo en fazla 26 kayıt tuttuğu için ek alan O(1).
from collections import Counter
def can_spell(note, banner):
stock = Counter(banner) # letter -> copies left
for ch in note:
if stock[ch] == 0:
return False # this letter has run out
stock[ch] -= 1
return True
print(can_spell("aab", "baa")) # -> True
print(can_spell("aa", "ab")) # -> False
print(can_spell("", "xyz")) # -> TrueKodda değil de fikirde mi takıldın? Frekans sayma bunu anlatıyor.