Tries & Strings

How it works

A trie stores a set of strings as a tree of characters. Every node is a prefix, and its children are the possible next characters. Words that share a beginning share the same path, so the dictionary is compressed and every prefix query is answered by walking at most L nodes.

The power is early stopping. When a search over a grid or a sentence reaches a prefix that no word has, the trie says so immediately and the whole branch is abandoned. That pruning is why word search with many target words uses a trie rather than searching each word separately.

Mark the end of a word with a flag on the node, not with the absence of children: 'car' and 'card' both live on the same path. Nodes can also carry extra data, such as a count of words passing through, the stored word itself, or the best suggestion.

Beyond tries, this topic covers string techniques that compare without rescanning: rolling hashes, prefix-function matching, and palindrome expansion. All share the goal of avoiding repeated character-by-character comparisons.

How to attack it

1. 1Check whether many queries share prefixes or whether a search can be pruned by prefix.
2. 2Choose the child structure: a map for general alphabets, a fixed array of 26 for lowercase letters.
3. 3Decide what each node stores beyond children (end flag, count, word).
4. 4Write insert and walk first; build every query on the walk.
5. 5For grid searches, remove or mark found words to avoid duplicates and speed up later searches.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_word = False
        self.count = 0       # words passing through this node


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.count += 1
        node.is_word = True

    def _walk(self, prefix):
        # Returns the node for prefix, or None as soon as a char is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

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

What it costs