# Tries — Part 2: Interview Problems

Six problems: implementing the trie, wildcard search, grid search over many words, prefix replacement and autocomplete.

## 1. Implement Trie (Prefix Tree) (LeetCode 208)

**🟠 Medium.** Implement `insert(word)`, `search(word)` and `startsWith(prefix)`.

```text
insert("apple"), search("apple") → true, search("app") → false, startsWith("app") → true
```

**Approach.** Nodes with a children map and an end flag. `insert` creates missing nodes along the path and marks the end; `search` and `startsWith` walk the path, and only `search` checks the end flag.

**Complexity.** O(L) per operation; space O(total characters inserted).

```typescript
class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode = this.root;
    for (const c of s) {
      const next = node.children.get(c);
      if (!next) return null;
      node = next;
    }
    return node;
  }
  search(word: string): boolean { const n = this.walk(word); return !!n && n.isEnd; }
  startsWith(prefix: string): boolean { return this.walk(prefix) !== null; }
}
```

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

    def search(self, word):
        node = self._walk(word)
        return bool(node and node.is_end)

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

## 2. Design Add and Search Words Data Structure (LeetCode 211)

**🟠 Medium.** Support `addWord(word)` and `search(pattern)` where `.` matches any single letter.

```text
addWord bad, dad, mad · search("pad") → false · search(".ad") → true · search("b..") → true
```

**Approach.** Trie plus DFS: for a normal character follow that child; for `.`, try every child. Return true if any branch reaches the end of the pattern on an end-of-word node.

**Complexity.** O(L) to add; search is O(L) without dots and up to O(26ᴸ) in the worst case with many dots.

```typescript
class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class WordDictionary {
  private root = new TrieNode();
  addWord(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  search(word: string): boolean {
    const dfs = (node: TrieNode, i: number): boolean => {
      if (i === word.length) return node.isEnd;
      const c = word[i];
      if (c === ".") {
        for (const child of node.children.values()) if (dfs(child, i + 1)) return true;
        return false;
      }
      const next = node.children.get(c);
      return !!next && dfs(next, i + 1);
    };
    return dfs(this.root, 0);
  }
}
```

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def add_word(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            c = word[i]
            if c == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            return c in node.children and dfs(node.children[c], i + 1)
        return dfs(self.root, 0)
```

## 3. Word Search II (LeetCode 212)

**🔴 Hard.** Return all dictionary `words` that can be traced on the letter grid (adjacent cells, each used once per word).

```text
board 4×4, words ["oath","pea","eat","rain"] → ["eat","oath"]
```

**Approach.** Build a trie of the words (store the full word at its end node). DFS from every cell, moving only along trie edges, so dead prefixes are abandoned immediately. When a node with a word is reached, record it and clear it (no duplicates); remove exhausted leaves to prune future searches.

**Complexity.** O(R · C · 4 · 3ᴸ⁻¹) in the worst case, but pruning makes it fast in practice; trie space O(total letters).

```typescript
type Node = { kids: Map<string, Node>; word: string | null };

function findWords(board: string[][], words: string[]): string[] {
  const root: Node = { kids: new Map(), word: null };
  for (const w of words) {
    let node = root;
    for (const c of w) {
      if (!node.kids.has(c)) node.kids.set(c, { kids: new Map(), word: null });
      node = node.kids.get(c)!;
    }
    node.word = w;
  }
  const R = board.length, C = board[0].length, found: string[] = [];
  const dfs = (r: number, c: number, parent: Node): void => {
    const ch = board[r][c], node = parent.kids.get(ch)!;
    if (node.word) { found.push(node.word); node.word = null; }
    board[r][c] = "#";
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && node.kids.has(board[nr][nc])) dfs(nr, nc, node);
    }
    board[r][c] = ch;
    if (node.kids.size === 0 && !node.word) parent.kids.delete(ch);
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (root.kids.has(board[r][c])) dfs(r, c, root);
  return found;
}
```

```python
def find_words(board, words):
    root = {}
    for w in words:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node["$"] = w                                  # word stored at its end
    R, C, found = len(board), len(board[0]), []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))                # record once
        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch)                             # prune an exhausted branch

    for r in range(R):
        for c in range(C):
            if board[r][c] in root:
                dfs(r, c, root)
    return found
```

## 4. Longest Common Prefix (LeetCode 14)

**🟢 Easy.** Return the longest common prefix of an array of strings.

```text
["flower","flow","flight"] → "fl"
```

**Approach.** Vertical scan: compare character i of every string until one differs or a string ends. (With a trie: insert all words and walk down while the node has exactly one child and isn't a word end. Useful when the set changes or queries repeat.)

**Complexity.** O(S) time for S total characters, O(1) extra space.

```typescript
function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return "";
  for (let i = 0; i < strs[0].length; i++) {
    for (const s of strs) if (i === s.length || s[i] !== strs[0][i]) return strs[0].slice(0, i);
  }
  return strs[0];
}
```

```python
def longest_common_prefix(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i == len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]
```

## 5. Replace Words (LeetCode 648)

**🟠 Medium.** Replace every word in `sentence` by the shortest dictionary root that is its prefix (if any).

```text
roots ["cat","bat","rat"], "the cattle was rattled by the battery" → "the cat was rat by the bat"
```

**Approach.** Insert roots into a trie. For each word, walk the trie character by character and stop at the first end-of-root node; that prefix is the replacement. If the walk falls off the trie first, keep the word.

**Complexity.** O(total characters) time.

```typescript
function replaceWords(dictionary: string[], sentence: string): string {
  type N = { [k: string]: N } & { $?: boolean };
  const root: N = {} as N;
  for (const w of dictionary) {
    let node = root;
    for (const c of w) node = (node[c] ??= {} as N);
    node.$ = true;
  }
  const shortest = (word: string): string => {
    let node = root;
    for (let i = 0; i < word.length; i++) {
      node = node[word[i]];
      if (!node) return word;
      if (node.$) return word.slice(0, i + 1);
    }
    return word;
  };
  return sentence.split(" ").map(shortest).join(" ");
}
```

```python
def replace_words(dictionary, sentence):
    root = {}
    for w in dictionary:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node["$"] = True

    def shortest_root(word):
        node = root
        for i, c in enumerate(word):
            if c not in node:
                return word
            node = node[c]
            if "$" in node:
                return word[:i + 1]
        return word

    return " ".join(shortest_root(w) for w in sentence.split())
```

## 6. Search Suggestions System (LeetCode 1268)

**🟠 Medium.** After each typed character of `searchWord`, return up to three lexicographically smallest products starting with the typed prefix.

```text
products [mobile, mouse, moneypot, monitor, mousepad], "mouse" → [[mobile,moneypot,monitor], …, [mouse,mousepad]]
```

**Approach.** Sort the products, insert them into a trie, and store at each node the first three products passing through it (sorted insertion makes them the smallest). Then walk the trie with the typed characters; once the walk falls off, every remaining prefix has no suggestions. (A sort + binary search solution is equally good.)

**Complexity.** O(S log S) to sort plus O(total characters) to build; O(L) to answer.

```typescript
function suggestedProducts(products: string[], searchWord: string): string[][] {
  type N = { kids: Map<string, N>; top: string[] };
  const root: N = { kids: new Map(), top: [] };
  for (const p of [...products].sort()) {
    let node = root;
    for (const c of p) {
      if (!node.kids.has(c)) node.kids.set(c, { kids: new Map(), top: [] });
      node = node.kids.get(c)!;
      if (node.top.length < 3) node.top.push(p);
    }
  }
  const res: string[][] = [];
  let node: N | undefined = root;
  for (const c of searchWord) {
    node = node?.kids.get(c);
    res.push(node ? node.top : []);
  }
  return res;
}
```

```python
def suggested_products(products, search_word):
    root = {}
    for p in sorted(products):
        node = root
        for c in p:
            node = node.setdefault(c, {"#": []})
            if len(node["#"]) < 3:
                node["#"].append(p)
    res, node = [], root
    for c in search_word:
        node = node.get(c) if node else None
        res.append(node["#"] if node else [])
    return res
```