Answers for "trie autocomplete pseudocode"

0

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
Posted by: Guest on August-27-2021

Browse Popular Code Answers by Language