Does this exact word exist?
Store every word as a path of letters from a shared root, one node per character. About 10 minutes.
Building the trie
For each word, start at the root and walk its letters. At every letter, if the current node has no child for it, create one. Then move into that child.
After the word's last letter, mark that node as an end. A dictionary of plain nested maps is enough: each node is a map from a letter to the next node.
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {})
node["#"] = TrueInsert "cat": walk from the root, creating c, a, t. Mark the last node: a word ends here.
Searching the trie
To check whether the target is one of the inserted words, walk its letters the same way, but never create a node. If a letter is missing, the target was never inserted, like looking for a street that isn't on the map.
If every letter is found, the target exists only if the final node is marked as an end.
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {})
node["#"] = True
node = root
for c in target:
if c not in node:
return False
node = node[c]
return node.get("#", False)Only "cat" is inserted. Does searching for "ca" find a word?
- ANo
- BYes, because "ca" is a valid path
Show the answer
No. The path for "ca" exists (as part of "cat"), but its node was never marked as an end.
Does this exact word exist?
words is a list of lowercase words. Return true if target is exactly one of the words in words, or false otherwise.
words = ["cat", "car", "dog"], target = "car" → true
0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, target.length ≤ 30 · every word is lowercase a-z