Kelime listesini tek string'e paketle
Görev tanımı
Problem
Bir string listesini tek bir string'e çeviren pack(words) ve o string'i orijinal listeye geri çeviren unpack(text) fonksiyonlarını yaz. Her kelime ondalık olarak uzunluğu, sonra bir #, sonra kelimenin kendisi olarak yazılır. Kelimeler boş olabilir ve rakamlar ile # dahil her karakteri içerebilir; bu yüzden unpack bir kelimenin içinde asla ayırıcı aramamalı.
Örnekler
Input: words = ["hi", "#1"]
Output: pack -> "2#hi2##1"
unpack -> ["hi", "#1"]
Neden: "2#" okunduktan sonra sonraki iki karakter, "#" olsun olmasın, bütün olarak alınır
Input: words = ["", "a"]
Output: pack -> "0#1#a"
Neden: boş bir kelime de uzunluğunu alır, böylece gidiş dönüşten sağ çıkar
Input: words = []
Output: pack -> ""
unpack -> []
Neden: edge case: yazılacak ve okunacak bir şey yok
İpuçları
0 / 3
Bir ayırıcıyla birleştirmek, bir kelime o ayırıcıyı içerdiği anda bozulur. Her kelimenin önündeki uzunluk belirsizliği ortadan kaldıran şey.
Bir uzunluktan sonraki ilk # her zaman o uzunluğun sonudur, çünkü bir uzunluk yalnız rakamlardan oluşur. Ondan sonraki her şey aranmaz, sayılır.
Bir okuma konumu tut. Bir sonraki #'e kadar rakamları tara, onları bir n sayısına çevir, #'ten sonraki tam olarak n karakteri al ve okuma konumunu onların ötesine taşı. Konum sona ulaşana kadar tekrarla.
- Hedef zaman
- O(L)
- Hedef alan
- O(L)
Kısıtlar
- words may be empty
- words may contain any character, including # and digits
Çözüm
Uzunluk prefix'i (önek) okuyucuya tam olarak kaç karakter alacağını söyler; bu yüzden bir kelimenin içeriği asla önemli değildir. Bir uzunluğu okumak güvenlidir, çünkü bir uzunluk yalnız rakamlardan oluşur; bu da ondan sonraki ilk #'i sayının gerçek sonu yapar. Paketlerken de açarken de her karakter sabit sayıda ziyaret edilir. Toplam L karakter için zaman O(L), çıktı için alan O(L).
def pack(words):
return "".join(f"{len(w)}#{w}" for w in words)
def unpack(text):
words, i = [], 0
while i < len(text):
hash_at = text.index("#", i) # end of the length digits
n = int(text[i:hash_at])
words.append(text[hash_at + 1:hash_at + 1 + n])
i = hash_at + 1 + n # jump over the word, never into it
return words
print(pack(["hi", "#1"])) # -> 2#hi2##1
print(unpack("2#hi2##1")) # -> ['hi', '#1']
print(unpack(pack(["", "a"]))) # -> ['', 'a']
print(unpack(pack([]))) # -> []Kodda değil de fikirde mi takıldın? String'leri encode ve decode etme bunu anlatıyor.