LeetCode 211 · Medium · Tries

Design Add and Search Words Data Structure

Build a dictionary with addWord(word) and search(word), where the search pattern may contain ., a wildcard that matches any single letter.

O(L)add · search without dots
O(26^d · L)search with d dots, worst case
trie + DFSa dot branches into every child

addWord w and search p, separated by ; · 1 to 10 calls · words a–z, patterns a–z and ., 1 to 5 characters

Calls → return value · yellow = running

dfs calls dfs(i, node): match word.substring(i) starting below node · newest on the right · dashed nodes = branches that failed

Pattern i = the position being matched

i
class TrieNode { Map<Character, TrieNode> children = new LinkedHashMap<>(); boolean word = false;}class WordDictionary { private TrieNode root; public WordDictionary() { root = new TrieNode(); } public void addWord(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) { cur.children.put(c, new TrieNode()); } cur = cur.children.get(c); } cur.word = true; } public boolean search(String word) { return dfs(word, 0, root); } private boolean dfs(String word, int j, TrieNode root) { TrieNode cur = root; for (int i = j; i < word.length(); i++) { char c = word.charAt(i); if (c == '.') { for (TrieNode child : cur.children.values()) { if (dfs(word, i + 1, child)) { return true; } } return false; } else { if (!cur.children.containsKey(c)) { return false; } cur = cur.children.get(c); } } return cur.word; }}
call
—
i, c
—
cur
—
return
—
nodes visited
0

Why it works

  1. Brute force stores a list and compares the pattern with every word of the same length, letter by letter: O(n·L) per search for n words.
  2. A letter has one way down; a dot has many. In the trie a normal letter follows exactly one edge. A dot could be any letter, so dfs tries each child in turn and stops at the first branch that matches the rest of the pattern. A branch that fails is abandoned as a whole (dashed).
  3. Cost: addWord and dot-free searches are O(L). Each dot can fan out to up to 26 children, so the worst case is O(26^d · L) for d dots; in practice a sparse trie prunes most branches after a letter or two.
  4. Pitfall: returning true when the pattern runs out on any node. The match must end on a node marked word: with only ab stored, search(".") reaches node a, which is not a word, so it is false.
  5. Related: Implement Trie (208) is the same structure without the wildcard; Word Search II (212) also lets a trie prune a branching search.