Implement Trie (Prefix Tree)

Problem

https://leetcode.com/problems/implement-trie-prefix-tree/

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.

• void insert(String word) Inserts the string word into the trie.

• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

 Input
 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
 [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
 Output
 [null,\
\ null, true, false, true, null, true]

 Explanation
 Trie trie = new Trie();
 trie.insert("apple");
 trie.search("apple");   // return True
 trie.search("app");     // return False
 trie.startsWith("app"); // return True
 trie.insert("app");
 trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000

• word and prefix consist only of lowercase English letters.

• At most 3 * 10:sup:`4` calls in total will be made to insert, search, and startsWith.

Pattern

Hash Table, String, Design, 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

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

    def __init__(self, char, end_of_word=False):
        self.char = char
        self.end_of_word = end_of_word
        self.children = {}


class Trie:
    """A prefix tree supporting insert, search, and prefix queries."""

    def __init__(self):
        self.root = TrieNode("<start_of_word>")

    def insert(self, word: str) -> None:
        """Insert ``word`` into the trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode(char)
            node = node.children[char]
        node.end_of_word = True

    def search(self, word: str) -> bool:
        """Return whether ``word`` is in the trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.end_of_word

    def startsWith(self, prefix: str) -> bool:
        """Return whether any word in the trie starts with ``prefix``."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Test

>>> from implement_trie_prefix_tree__trie import Trie
>>> t = Trie()
>>> t.insert("apple")
>>> t.search("apple")
True
>>> t.search("app")
False
>>> t.startsWith("app")
True
>>> t.insert("app")
>>> t.search("app")
True

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 implement_trie_prefix_tree__trie.TrieNode(char, end_of_word=False)

Bases: object

Node in the trie.

class implement_trie_prefix_tree__trie.Trie

Bases: object

A prefix tree supporting insert, search, and prefix queries.

insert(word: str) → None

Insert word into the trie.

search(word: str) → bool

Return whether word is in the trie.

startsWith(prefix: str) → bool

Return whether any word in the trie starts with prefix.