İçeriğe geç

Prefix'e göre değer toplamı

Kolay#trie#design~20 dk

Görev tanımı

Problem

Tam sayı değerli string anahtarlardan oluşan, iki işlemli bir depo tasarla. put(key, value) bir anahtarın değerini ayarlar; anahtar zaten saklıysa eski değerin yerine geçer. total(prefix) prefix (önek) ile başlayan bütün anahtarların değerlerinin toplamını, hiç yoksa 0 döndürür. İki işlem de argümanlarının uzunluğuyla orantılı zamana mal olmalı.

Örnekler

Input:  put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Neden: iki put'tan sonra "ap" iki anahtarı da, "apple" yalnız birini başlatıyor
Input:  put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Neden: "apple"ın ikinci put'u 3'ü üzerine eklemek yerine 5 ile değiştiriyor
Input:  put("apple", 3), total("b")
Output: 0
Neden: edge case: hiçbir anahtar prefix ile başlamıyor

İpuçları

0 / 3

Hedef zaman
O(L)
Hedef alan
O(total characters)

Kodda değil de fikirde mi takıldın? Prefix arama bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır