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.

Keep a best so far: update it every time an end marker is passed.

Don't stop early: a longer match can only be found by continuing the walk.

In code

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

words = [a, ab, abc], target = "abcd"

best: "a"

'a': the node is an end, so "a" is a known word. Remember it, but keep walking.

Move 1 of 4

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.

No match at all: answer with the empty string if no end marker was ever crossed.