:orphan:

Tries
=====

.. highlight:: none

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



.. highlight:: python

Pattern
-------
Trie

Solution
--------
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
----

.. literalinclude:: ../problems/medium/tries/tries__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from tries__approach_1 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
----------
| :math:`n` is the length of the string to insert
| Insertion Time: :math:`O(n)` — to insert a string of length :math:`n` into the trie, we need to create at most :math:`n` nodes
| Search Time: :math:`O(n)` — to find the node corresponding to the last character of the input string, we need to traverse :math:`n` nodes
| Space: :math:`O(n)` — trie node storage

.. autoclass:: tries__approach_1.TrieNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autoclass:: tries__approach_1.Trie
   :members:
   :show-inheritance:
   :undoc-members: