Tries

Problem¶

Implement tries in Python with insert(), search() and startwith() methods.

A trie is ree for strings where each edge is a character and each node stores whether a word ends there.

So:

Nodes represent prefix states.
Edges are labeled with characters.

insert: "cat", "car"

root
 └─ c
    └─ a
       ├─ t*
       └─ r*

Or more precisely:

root
 │  c
 └───── .
        │  a
        └───── .
               │  t
               └───── .*
               │  r
               └───── .*

where

. is the node.
c, a, t, r are edge labels.
* marks a node where a full word ends.

Key trick¶

Characters label edges, while each node represents the prefix along its path; is_word marks whether that prefix is also a complete word.

Trap¶

search() must check is_word, unlike startswith(); also, using setdefault with self.Node() would eagerly allocate unused nodes for existing edges.

Why is it interesting?¶

A trie shares common prefixes and supports insertion, exact lookup, and prefix lookup in \(O(L)\) time for an input of length \(L\).

Python solution¶

class Trie:
    class Node:
        def __init__(self):
            self.children = {}
            self.is_word = False

    def __init__(self):
        self.root = self.Node()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = self.Node()
            node = node.children[ch]
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

    def startswith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True