Pular para o conteúdo

Achar palavras do dicionário em um texto

Fácil#trie#prefix-pruning~15 min

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

Tempo-alvo
O(n · L + W)
Espaço-alvo
O(W + n · L)

Restrições

  • the words are distinct

Travou na ideia, e não no código? Word Search com trie explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado