Data structures problem 25 of 30

Build a trie

Data structures
Medium

Implement a Trie (prefix tree) class with insert(word), search(word), which checks for a whole word, and starts_with(prefix).

t = Trie()
t.insert("car")
t.insert("cart")
t.search("car")        # True
t.search("ca")         # False
t.starts_with("ca")    # True
t.starts_with("dog")   # False

Show hint

Each node can be a dictionary from a character to the next node. You also need a way to mark "a word ends here".

Show solution

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["end"] = True

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and "end" in node

    def starts_with(self, prefix):
        return self._find(prefix) is not None

Each operation takes time proportional to the length of the word, however many words are stored. The "end" marker is safe because every real key is a single character. Tries power autocomplete and spell checkers, where "every word starting with ca" is the main question.

Want a problem like this every day? See today's problem and keep a streak going.