trie autocomplete pseudocode
def keys_with_prefix(root: Node, prefix: str) -> List[str]:
results: List[str] = []
x = _get_node(root, prefix)
_collect(x, list(prefix), results)
return results
def _collect(x: Optional[Node], prefix: List[str], results: List[str]) -> None:
"""
Append keys under node `x` matching the given prefix to `results`.
prefix: list of characters
"""
if x is None:
return
if x.value is not None:
prefix_str = ''.join(prefix)
results.append(prefix_str)
for c in x.children:
prefix.append(c)
_collect(x.children[c], prefix, results)
del prefix[-1] # delete last character
def _get_node(node: Node, key: str) -> Optional[Node]:
"""
Find node by key. This is the same as the `find` function defined above,
but returning the found node itself rather than the found node's value.
"""
for char in key:
if char in node.children:
node = node.children[char]
else:
return None
return node