Saltar al contenido

Suma de valores por prefijo

Fácil#trie#design~20 min

La misión

Problema

Diseña un almacén de claves de tipo string (cadena) con valores enteros y dos operaciones. put(key, value) asigna el valor de una clave y reemplaza el anterior si la clave ya existe. total(prefix) devuelve la suma de los valores de las claves que empiezan con el prefijo, o 0 si no hay ninguna. Ambas operaciones deben costar un tiempo proporcional a la longitud de su argumento.

Ejemplos

Input:  put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Por qué: después de los dos put, "ap" es el comienzo de ambas claves y "apple" solo de una
Input:  put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Por qué: el segundo put de "apple" reemplaza 3 por 5 en vez de sumarle
Input:  put("apple", 3), total("b")
Output: 0
Por qué: caso límite: ninguna clave empieza con el prefijo

Pistas

0 / 3

Tiempo objetivo
O(L)
Espacio objetivo
O(total characters)

¿Lo que te frena es la idea y no el código? Búsqueda por prefijo lo explica.

Python 3Ctrl+Enter ejecuta