Design Add and Search Words Data Structure
Construa um dicionário de palavras com duas operações. addWord w armazena a palavra w. search p informa se alguma palavra armazenada corresponde ao padrão p: mesmo comprimento e, em cada posição, o padrão contém a mesma letra ou um ponto ., que representa qualquer letra.
A operação i é ops[i] aplicada à palavra ou ao padrão words[i]. Execute-as em ordem em um dicionário vazio e retorne uma string para cada uma: "null" para um addWord, "true" ou "false" para uma search.
Função
- opsstring-array
- as operações, na ordem em que são executadas
- wordsstring-array
- a palavra a ser adicionada ou o padrão a ser pesquisado, um por operação
- Retornastring-array
- uma resposta por operação, como texto
Restrições
1 ≤ ops.length ≤ 2500words.length == ops.length- Cada
ops[i]éaddWordousearch. 1 ≤ words[i].length ≤ 20- A palavra a ser adicionada contém apenas letras minúsculas do inglês.
- Um padrão a ser pesquisado contém letras minúsculas do inglês e no máximo 3 pontos.
Exemplos
- Entrada
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- Saída
- ["null", "null", "true", "false", "false", "true"]
- Explicação
r.secorresponde às duas palavras: o ponto cobre o o derosee o i derise. Um ponto nunca representa uma letra ausente, entãoroserose.não correspondem...s.corresponde, pois ambas as palavras têm s na terceira posição.
- Entrada
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- Saída
- ["false", "null", "true", "true", "false"]
- Explicação
- O dicionário começa vazio, então
...não encontra nada. Depois queskyé adicionado,...es.ycorrespondem a ele, enquantoské curto demais.
- Entrada
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- Saída
- ["null", "null", "true", "false", "true"]
- Explicação
- O primeiro ponto de
ma..opode ser o p demapleou o n demango;mapletermina em e, masmangose encaixa. Nenhuma palavra termina em y, entãom...ynão funciona, em.p.ecorresponde amaple.
Para ir além
Como você ampliaria search se um padrão também pudesse conter *, representando qualquer sequência de letras, inclusive uma vazia?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Sem pontos, um conjunto hash das palavras armazenadas responderia a cada busca com uma única consulta. Um ponto muda isso:
c.tpoderia sercat,cotoucut. Que estrutura permite percorrer uma palavra uma letra por vez e ver todas as letras que podem vir em seguida?Armazene as palavras em uma trie, com um sinalizador em cada nó onde uma palavra armazenada termina. Uma letra no padrão segue um link filho. Um ponto pode ser qualquer letra, então é preciso testar cada filho do nó atual e voltar quando um ramo chegar a um beco sem saída.
Escreva uma
match(node, i)recursiva. No fim do padrão, responda com a flag de fim do nó. Em uma letra, siga esse filho ou falhe se ele não existir. Em um ponto, retorne true assim quematch(child, i+1)tiver sucesso para algum filho, e false se nenhum tiver.
Solução
Um ponto significa que a busca não pode nomear a palavra que procura: ma..o representa 676 palavras possíveis, e só importam as que estão armazenadas. Em uma trie, palavras que começam da mesma forma compartilham um caminho. Uma letra no padrão segue um link, um ponto se ramifica apenas para filhos existentes, e uma busca em profundidade retrocede a partir de ramos sem saída.
Compare o padrão com cada palavra armazenada
Intuição
Mantenha as palavras adicionadas em uma lista e teste cada uma com o padrão: mesmo comprimento e, em cada posição, um ponto ou a mesma letra. Essa é a definição de correspondência, verificada em relação a cada palavra armazenada, então a resposta está correta.
Cada busca percorre a lista inteira, O(n·L) para n palavras de até L letras, mesmo um padrão sem ponto. 1,250 adições seguidas de 1,250 buscas testam 1,250 × 1,250 = 1,562,500 palavras.
Algoritmo
- Mantenha as palavras adicionadas em uma lista. Para
addWord w, acrescentewe registre"null". - Para
search p, comparepcom cada palavra do mesmo comprimento, posição por posição, permitindo que um ponto corresponda a qualquer letra. - Registre
"true"na primeira correspondência ou"false"se não houver nenhuma.
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return resultTrie com uma busca em profundidade em pontos
Intuição
Coloque as palavras em uma trie: rose e rise compartilham o nó r, depois se dividem em o e i. Uma flag de término marca cada nó onde uma palavra armazenada termina. Um padrão de letras é um percurso pela trie. Um ponto pode ser qualquer letra; portanto, em um ponto, tente cada filho existente e retorne true assim que um deles levar a uma correspondência.
Para ma..o, o nó de ma tem os filhos p e n. Pelo p, o segundo ponto chega a l, que não tem filho o, então a busca volta e tenta n: g, depois o, que encerra mango.
Uma correspondência precisa consumir todo o padrão em um nó sinalizado, o que resolve a questão do comprimento: ros para em um nó não sinalizado, e rose. fica sem links. Um ponto abre no máximo 26 ramificações, então d pontos visitam no máximo 26^d · L nós, e um padrão sem pontos custa O(L).
Algoritmo
- Cada nó tem links para os filhos e uma flag de término, desativada inicialmente.
- Para
addWord w: percorrawa partir da raiz, criando os nós ausentes, e defina a flag de término onde a busca parar. match(node, i): seifor o comprimento do padrão, retorne a flag de término do nó.- Se
p[i]for uma letra, retorne false se o filho correspondente estiver ausente; caso contrário,match(child, i+1). Se for um ponto, retorne true sematch(child, i+1)for bem-sucedido para qualquer filho existente; caso contrário, false. - Registre
match(root, 0)para cada busca e"null"para cada adição.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
Armadilhas e casos extremos
- Deixar que o primeiro filho decida se há um ponto. Em
ma..o, o ramo p falha e o ramo n tem sucesso, então o código que retorna o resultado do primeiro filho responde falso quando tenta p primeiro. Responda falso somente depois que todos os filhos falharem. - Responder verdadeiro quando o padrão acaba em qualquer nó. Depois de adicionar
rose,roschega a um nó, mas nenhuma palavra termina ali. Verifique a flag de fim. - Deixar que um ponto corresponda a uma letra ausente.
card.corresponde acards, mas não acard. - Tratar um ponto como uma letra. Indexar um array de 26 posições com
'.' - 'a'lê fora do array; portanto, verifique primeiro se é um ponto.
Perguntas frequentes3
Qual é a complexidade de tempo de Add e Search Words?
Adicionar uma palavra de comprimento L leva O(L), assim como uma busca sem pontos, independentemente de quantas palavras estejam armazenadas. Uma busca com d pontos leva O(26^d · L) no pior caso. O uso de memória é de O(T) nós para T letras adicionadas.
Você consegue resolver isso com um conjunto hash em vez de uma trie?
Sim, com ressalvas. Um conjunto responde a um padrão sem pontos em uma única consulta. Para os pontos, você pode percorrer todas as palavras armazenadas desse comprimento, O(n·L), ou substituir cada ponto por todas as 26 letras e consultar cada resultado, 17.576 consultas para três pontos.
A busca na trie deve ser recursiva ou iterativa?
Ambos funcionam. A recursão avança um nível por letra do padrão, no máximo 20 neste caso, então a pilha de chamadas permanece pequena. Uma versão iterativa mantém uma pilha de pares (nó, posição) e empilha cada filho em um ponto.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def wordDictionaryOps(ops, words):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Saída Esperada
["null", "null", "true", "false", "false", "true"]