Pular para o conteúdo

Soma de valores por prefixo

Fácil#trie#design~20 min

A missão

Problema

Projete um armazenamento de chaves string com valores inteiros e duas operações. put(key, value) define o valor de uma chave, substituindo o valor antigo se a chave já estiver armazenada. total(prefix) retorna a soma dos valores de todas as chaves que começam com o prefixo, ou 0 se não houver nenhuma. As duas operações devem custar tempo proporcional ao comprimento do seu argumento.

Exemplos

Input:  put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Por quê: depois dos dois puts, "ap" inicia as duas chaves e "apple" inicia só uma
Input:  put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Por quê: o segundo put de "apple" substitui 3 por 5 em vez de somar
Input:  put("apple", 3), total("b")
Output: 0
Por quê: edge case: nenhuma chave começa com o prefixo

Dicas

0 / 3

Tempo-alvo
O(L)
Espaço-alvo
O(total characters)

Travou na ideia, e não no código? Busca por prefixo explica isso.

Python 3Ctrl+Enter executa