The longest prefix that is a word
Walk target through the trie, remembering the last point where an end marker was seen. About 9 minutes.
Walk and remember
Walk the target one letter at a time. Every time the current node is marked as an end, the part you've walked so far is a known word. Remember it as the best so far, but keep walking: a longer known word might still be ahead.
It is like noting each town you pass on a long road: the last one you pass is the furthest you got.
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {})
node["#"] = True
node = root
best = ""
for i, c in enumerate(target):
if c not in node:
break
node = node[c]
if node.get("#", False):
best = target[: i + 1]
return best- best
- "a"
'a': the node is an end, so "a" is a known word. Remember it, but keep walking.
When the walk ends
The walk stops either because the target runs out of letters, or because a letter is missing from the trie. Either way, whatever you remembered as the best match is the answer.
If you never crossed an end marker, there is no known word at the start of the target, so the answer is the empty string.
words = ["a", "ab"], target = "abc". What is the longest known prefix?
- A"ab"
- B"a"
Show the answer
"ab". Both "a" and "ab" are known words along the walk; "ab" is the longer one.
The longest prefix that is a word
words is a list of lowercase words. Return the longest prefix of target that is itself one of the words in words, or an empty string if none of them are a prefix of target.
words = ["a", "ab", "abc"], target = "abcd" → "abc"
0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, target.length ≤ 30 · every word is lowercase a-z