Spot Dictionary Words in a Text
Problem
Given a string text and a list of distinct words, return every pair [i, j] such that the slice of text from index i to index j, both included, is one of the words. Occurrences may overlap. Return the pairs sorted by i, then by j.
Examples
Input: text = "bytesofcode", words = ["byte", "bytes", "code", "of", "so"]
Output: [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
Why: byte, bytes, so, of and code, where so and of share the letter oInput: text = "ababa", words = ["aba", "ab"]
Output: [[0, 1], [0, 2], [2, 3], [2, 4]]Input: text = "abc", words = ["d"]
Output: []
Why: edge case, no word occursHints
0 / 3
Checking every slice of the text against a set of words works, but it builds O(n²) slices, most of which start no word at all.
From a fixed start index, a prefix tree lets you extend the slice one letter at a time and stop the moment no word continues with that letter.
Insert every word into a trie with an end marker. For each start i, walk the trie along text[i], text[i + 1] and so on, record [i, j] whenever the node marks the end of a word, and stop when the next letter has no child.
Solution
The trie turns each start position into a walk that stops as soon as the text leaves every word, the same pruning that makes a trie-driven grid search fast: a set of words can only answer whether a whole slice is a word, while a trie also answers whether the slice can still become one. Walking from start i in increasing j reports the matches for that start in increasing order, and the starts are visited in order, so the output needs no sort. For a text of length n and a longest word of length L, time is O(n · L) plus O(W) to build the trie from W total letters, and space is 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"])) # -> []Stuck on the idea rather than the code? Word Search With a Trie covers it.