Achar palavras do dicionário em um texto
A missão
Problema
Dada uma string text e uma lista de words distintas, retorne todo par [i, j] tal que o trecho de text do índice i ao índice j, ambos incluídos, seja uma das palavras. As ocorrências podem se sobrepor. Retorne os pares ordenados por i e depois por j.
Exemplos
Input: text = "bytesofcode", words = ["byte", "bytes", "code", "of", "so"]
Output: [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
Por quê: byte, bytes, so, of e code, em que so e of compartilham a letra o
Input: text = "ababa", words = ["aba", "ab"]
Output: [[0, 1], [0, 2], [2, 3], [2, 4]]
Input: text = "abc", words = ["d"]
Output: []
Por quê: edge case: nenhuma palavra aparece
Dicas
0 / 3
Comparar cada trecho do texto com um conjunto de palavras funciona, mas isso monta O(n²) trechos, e a maioria deles nem começa uma palavra.
A partir de um índice inicial fixo, uma trie permite estender o trecho uma letra por vez e parar no instante em que nenhuma palavra continua com aquela letra.
Insira cada palavra em uma trie com um marcador de fim. Para cada início i, percorra a trie seguindo text[i], text[i + 1] e assim por diante, registre [i, j] sempre que o nó marcar o fim de uma palavra e pare quando a próxima letra não tiver filho.
- Tempo-alvo
- O(n · L + W)
- Espaço-alvo
- O(W + n · L)
Restrições
- the words are distinct
Solução
A trie (árvore de prefixos) transforma cada posição inicial em um percurso que para assim que o texto sai de todas as palavras, a mesma poda que deixa rápida uma busca em grid guiada por trie: um conjunto (set) de palavras só consegue responder se um trecho inteiro é uma palavra, enquanto uma trie também responde se o trecho ainda pode virar uma. Percorrer a partir do início i com j crescente reporta as correspondências desse início em ordem crescente, e os inícios são visitados em ordem, então a saída não precisa de ordenação. Para um texto de comprimento n e uma palavra mais longa de comprimento L, o tempo é O(n · L) mais O(W) para construir a trie a partir de W letras no total, e o espaço é O(W).
def word_positions(text, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = True # a word ends here
found = []
for i in range(len(text)):
node = root
for j in range(i, len(text)):
node = node.get(text[j])
if node is None: # no word continues this way
break
if "$" in node:
found.append([i, j])
return found
print(word_positions("bytesofcode", ["byte", "bytes", "code", "of", "so"])) # -> [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
print(word_positions("ababa", ["aba", "ab"])) # -> [[0, 1], [0, 2], [2, 3], [2, 4]]
print(word_positions("abc", ["d"])) # -> []Travou na ideia, e não no código? Word Search com trie explica isso.