En uzun ortak prefix
Görev tanımı
Problem
Bir kelime koleksiyonu verildiğinde, her kelimenin başladığı en uzun açılış karakter bloğunu bul. Blok her kelimenin ilk karakterinden başlamalı; yani bir kelimede daha sonra görünen bir eşleşme sayılmaz. Kelimeler hiçbir açılış karakterini paylaşmıyorsa boş metni döndür.
Örnekler
Input: words = ["flower", "flow", "flight"]
Output: "fl"
Neden: üçüncü kelime uyumu üçüncü karakterde bozuyor
Input: words = ["dog", "racecar"]
Output: ""
Neden: kelimeler hemen anlaşamıyor
Input: words = []
Output: ""
Neden: edge case: karşılaştırılacak kelime yok
İpuçları
0 / 3
Kelimeleri çiftler halinde birbiriyle karşılaştırmak gerekenden fazla iş. Cevap hiçbir kelimeden uzun olamaz, yani tek bir kelime ölçüt olarak kullanılabilir.
Kelimeleri alt alta diz ve kelimeler yerine sütunlar halinde düşün. Cevap anlaşmayı bıraktıkları ilk sütunda biter.
İlk kelimenin karakterlerini konuma göre dolaş. Her konumda diğer her kelimenin yeterince uzun olduğunu ve orada aynı karakteri taşıdığını kontrol et. İlk başarısızlık prefix'i o konumda bitirir; her konumdan sağ çıkmak da bütün ilk kelimenin prefix olduğu anlamına gelir.
- Hedef zaman
- O(total characters)
- Hedef alan
- O(len(words) + len(words[0]))
Çözüm
Cevap ilk kelimeyi asla aşamaz; bu yüzden o kelime ölçüt görevi görür ve arama onun konumları üzerindedir. Sütun sütun (column) taramak, herhangi bir kelimenin çok kısa olduğu ya da anlaşmadığı ilk konumda durur; ortak prefix'in (önek) bittiği yer de tam olarak orasıdır. Kelimeyi kelimeyle değil, her sütunda bütün kelimeleri karşılaştırmak taramanın olabildiğince erken durması demektir. En kötü durumda zaman O(toplam karakter), döndürülen dilim dışında alan O(1).
def longest_shared_prefix(words):
if not words:
return ""
for i, ch in enumerate(words[0]): # walk the yardstick word column by column
for word in words[1:]:
if i >= len(word) or word[i] != ch:
return words[0][:i] # this column breaks the agreement
return words[0] # every column survived the check
print(longest_shared_prefix(["flower", "flow", "flight"])) # -> fl
print(longest_shared_prefix(["dog", "racecar"])) # ->
print(longest_shared_prefix([])) # ->Kodda değil de fikirde mi takıldın? String temelleri bunu anlatıyor.