Tries

Problem

https://www.hackerrank.com/challenges/ctci-contacts/problem

Pattern

Trie

Approaches

Trie

Explanation

https://www.youtube.com/watch?v=zIjfhVPRZCg

A trie is a tree filled such that each node is a character and successive characters in words are descendents. Tries can be used for dictionary autocompletion. By scanning descendant branches, we can list all words that start with a given substring. The root is a special start of sequence (SOS) character and the ends of words are denoted using a special end of sequence character (EOS).

                l - e - EOS
               /
SOS - a - p - p - EOS
       \\
        x - e - EOS

Code

from __future__ import annotations

SOS_char = "<"
EOS_char = ">"


class TrieNode:
    """Node in the trie."""

    def __init__(self, char: str):
        self.char: str = char
        self.children: list[TrieNode] = []

    def add_child(self, node: TrieNode):
        self.children.append(node)

    def get_child(self, char) -> TrieNode | None:
        for child in self.children:
            if char == child.char:
                return child
        return None

    def descendant_strings(self, string: str):
        strings: list[str] = []
        for child in self.children:
            if child.char == EOS_char:
                strings.append(string + self.char)
            else:
                strings.extend(child.descendant_strings(string + self.char))
        return strings


class Trie:
    """Implemented as a n-ary tree of nodes."""

    def __init__(self):
        self.root = TrieNode(SOS_char)

    def add(self, string: str):
        node = self.root
        for char in string:
            child = node.get_child(char)
            if child is not None:
                node = child
            else:
                new_node = TrieNode(char)
                node.add_child(new_node)
                node = new_node
        EOS = TrieNode(EOS_char)
        node.add_child(EOS)

    def strings_starting_with(self, string: str) -> list[str]:
        # loop to end of string
        node = self.root
        for char in string:
            # check that path can continue
            child = node.get_child(char)
            if child is not None:
                node = child
            else:
                return []
        return node.descendant_strings(string[:-1])

Test

>>> from tries__trie import Trie
>>> trie = Trie()
>>> trie.add('apple')
>>> trie.add('axiom')
>>> trie.add('animal')
>>> trie.add('bees')
>>> trie.strings_starting_with('a')
['apple', 'axiom', 'animal']
>>> trie.strings_starting_with('b')
['bees']

Complexity

\(n\) is the length of the string to insert

Measure	Complexity	Notes
Insertion Time	\(O(n)\)	to insert a string of length \(n\) into the trie, we need to create at most \(n\) nodes
Search Time	\(O(n)\)	to find the node corresponding to the last character of the input string, we need to traverse \(n\) nodes
Space	\(O(n)\)	trie node storage

class tries__trie.TrieNode(char: str)

Bases: object

Node in the trie.

add_child(node: TrieNode)

descendant_strings(string: str)

get_child(char) → TrieNode | None

class tries__trie.Trie

Bases: object

Implemented as a n-ary tree of nodes.

add(string: str)

strings_starting_with(string: str) → list[str]