AlgoAtlas

Tries

Phase 2 4 solutions

Tries

mindmap
  root((Tries))
    Basic Trie
      Implement Trie Prefix Tree LC208
    Wildcard Search
      Design Add And Search Words LC211
    Trie + DP
      Extra Characters in a String LC2707
    Trie + Backtracking
      Word Search II LC212

Problem List

# Problem LC Difficulty
1 Implement Trie Prefix Tree 208 🟡 Medium
2 Design Add And Search Words 211 🟡 Medium
3 Extra Characters in a String 2707 🟡 Medium
4 Word Search II 212 🔴 Hard

Approach Diagrams

Trie Node Structure

flowchart TD
    A["TrieNode<br/>─────────────<br/>children: dict[char → TrieNode]<br/>is_end: bool"] --> B["Example: insert 'cat'"]
    B --> C["root<br/> children: c → ..."]
    C --> D["c-node<br/> children: a → ..."]
    D --> E["a-node<br/> children: t → ..."]
    E --> F["t-node<br/> is_end = True"]

Insert / Search / StartsWith Operations

flowchart TD
    A[Operation] --> B{Type}
    B -- insert word --> C[node = root]
    C --> D[For each char in word]
    D --> E{"char in<br/>node.children?"}
    E -- No --> F[Create new TrieNode]
    E -- Yes --> G[Move to child]
    F --> G
    G --> D
    D --> H["Mark last node<br/>is_end = True"]
    B -- search word --> I[node = root]
    I --> J[For each char in word]
    J --> K{"char in<br/>node.children?"}
    K -- No --> L[Return False]
    K -- Yes --> M[Move to child]
    M --> J
    J --> N[Return node.is_end]
    B -- startsWith prefix --> O["Same as search<br/>but return True<br/>if all chars found"]

Wildcard Search with DFS — LC 211

flowchart TD
    A[search word with dots] --> B[DFS from root]
    B --> C[For each char in word]
    C --> D{char == dot?}
    D -- Yes --> E["Recurse into ALL<br/>children nodes"]
    D -- No --> F{"char in<br/>node.children?"}
    F -- No --> G[Return False]
    F -- Yes --> H[Move to child]
    E --> I{"Any child<br/>returns True?"}
    I -- Yes --> J[Return True]
    I -- No --> G
    H --> C
    C --> K[Return node.is_end]

Trie + Backtracking — Word Search II (LC 212)

flowchart TD
    A[Build Trie from word list] --> B[DFS on each board cell]
    B --> C{"char at cell<br/>in trie node children?"}
    C -- No --> D[Prune: return early]
    C -- Yes --> E[Move to trie child node]
    E --> F{node.is_end?}
    F -- Yes --> G["Add word to results<br/>mark node.is_end = False<br/>to avoid duplicates"]
    F -- No --> H[Continue DFS]
    G --> H
    H --> I["Mark cell visited<br/>explore 4 neighbors"]
    I --> J["Unmark cell<br/>backtrack"]
    J --> K{"Trie node has<br/>no children left?"}
    K -- Yes --> L["Prune trie branch<br/>for efficiency"]
    K -- No --> B

When to Use Trie vs HashMap

flowchart TD
    A[String lookup problem] --> B{"Need prefix<br/>operations?"}
    B -- Yes --> C{How many words?}
    C -- Many, shared prefixes --> D["Trie<br/>space-efficient<br/>LC 208, 211, 212"]
    C -- Few words --> E[HashSet is fine]
    B -- No --> F{Exact match only?}
    F -- Yes --> G["HashMap / HashSet<br/>simpler, O1 lookup"]
    F -- No, need wildcard --> H["Trie + DFS<br/>LC 211"]
    A --> I{"Need to find all<br/>words in a grid?"}
    I -- Yes --> J["Trie + Backtracking<br/>LC 212<br/>better than running<br/>search per word"]
    A --> K{"DP with word<br/>boundary checks?"}
    K -- Yes --> L["Trie speeds up<br/>boundary lookup<br/>LC 2707"]

Complexity Summary

Problem Time Space Notes
Insert (208) O(L) O(L) L = word length
Search (208) O(L) O(1)
StartsWith (208) O(L) O(1)
Add & Search (211) O(L) insert, O(26^L) search worst O(total chars) Dot triggers full DFS
Extra Characters (2707) O(n² · L) O(total chars) DP + trie lookup
Word Search II (212) O(m·n · 4^L) O(total chars) Trie prunes repeated searches

L = average word length, m·n = board size

Study Order

flowchart LR
    S1["Step 1<br/>Implement Trie 208<br/>Build the data structure"]
    S2["Step 2<br/>Add & Search Words 211<br/>Add wildcard DFS"]
    S3["Step 3<br/>Extra Characters 2707<br/>Trie + DP"]
    S4["Step 4<br/>Word Search II 212<br/>Trie + Backtracking"]
    S1 --> S2 --> S3 --> S4

Key insight: A Trie is just a tree where each edge is a character. Its power is shared prefixes — instead of storing "cat", "car", "card" three times, they share the "ca" path. Always implement LC 208 from scratch before attempting the others.

Tries (Prefix Trees)

Core Intuition

A trie stores strings character by character in a tree. Each node represents a prefix. Use when you need fast prefix lookups, autocomplete, or searching a dictionary of words.

  • TrieNode: children map (dict or array[26]) + is_end flag
  • Insert: Walk/create nodes for each character
  • Search: Walk nodes; check is_end at last char
  • StartsWith: Same as search but don't require is_end
  • Wildcard: DFS with branching on '.' nodes
  • Trie + Backtracking: Build trie from word list, then DFS grid

Decision Flowchart

flowchart TD
    A[Trie Problem] --> B{Operation needed?}
    B -->|Insert / exact search / prefix| C["Standard Trie<br/>Implement Trie LC 208"]
    B -->|Wildcard / regex search| D["DFS through trie<br/>on dot branch all children<br/>Add Search Words LC 211"]
    B -->|Find min extra chars| E["Trie + DP<br/>Extra Characters LC 2707"]
    B -->|Find multiple words in grid| F["Build trie from words<br/>DFS grid with trie node<br/>Word Search II LC 212"]
    F --> G{Optimization?}
    G -->|Prune found words| H["Delete leaf nodes after finding<br/>prevent re-visiting"]
    G -->|Prune dead branches| I["Track word count in subtree<br/>delete when count=0"]

Problems

Implement Trie (Prefix Tree) — LC 208 | Medium

  • Learn: TrieNode with children: dict and is_end: bool; implement insert, search, startsWith
  • Mistake: Using a flat dict of full strings (defeats the purpose; doesn't support prefix queries efficiently)
  • Complexity: O(m) per operation where m = word length; O(n·m) space total
  • Edge: Empty string insert/search; searching prefix that is also a full word; duplicate inserts

Add and Search Words — LC 211 | Medium

  • Learn: Standard trie insert; search uses DFS — on '.', recurse into all children
  • Mistake: Iterative search doesn't handle '.' cleanly; use recursive DFS
  • Complexity: O(m) insert, O(26^m) worst-case search (all dots), O(n·m) space
  • Edge: Pattern is all dots; pattern longer than any inserted word; empty pattern

Extra Characters in a String — LC 2707 | Medium

  • Learn: Build trie from dictionary; dp[i] = min extra chars in s[0..i-1]; at each i, try all substrings s[j..i-1] in trie
  • Mistake: Using set lookup instead of trie (both work, but trie is the intended pattern); not initializing dp[0]=0
  • Complexity: O(n²) time with trie traversal, O(n + d·m) space where d=dict size, m=avg word length
  • Edge: No dictionary words match → return len(s); entire string is one dictionary word → 0

Word Search II — LC 212 | Hard

  • Learn: Build trie from words; DFS from each grid cell tracking current trie node; add word when node.word is set
  • Mistake: Running separate Word Search I for each word (O(words × m×n × 4^L)); trie shares prefixes
  • Optimization: After finding a word, set node.word = None to avoid duplicates; prune trie nodes with no children
  • Complexity: O(m·n·4·3^(L-1)) time where L=max word length, O(total chars in words) space
  • Edge: Duplicate words in input (deduplicate or use node.word=None trick); single cell grid; word not in grid

General Edge Cases

  • Empty string operations
  • Words with common prefixes (core trie use case — should work correctly)
  • Very long words vs short words in same trie
  • Duplicate words in word list (Word Search II)
  • Grid with all same characters
  • Dictionary word that is a prefix of another dictionary word
  • Case sensitivity (problems typically lowercase only)
# Problem LC Difficulty
1 Implement Trie Prefix Tree 208 🟡 Medium
2 Design Add And Search Words 211 🟡 Medium
3 Extra Characters in a String 2707 🟡 Medium
4 Word Search II 212 🔴 Hard
Design Add And Search Words ▼ expand 
"""
# 211: Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding whether a
string matches any previously added string, where the search word may contain
`'.'` wildcards that each match any single letter.

## Examples
```text
Input:  addWord("bad"); addWord("dad"); addWord("mad")
        search("pad"); search("bad"); search(".ad"); search("b..")
Output: False; True; True; True
```

## Constraints
- 1 <= word.length <= 25
- Words in addWord consist of lowercase English letters.
- Words in search consist of '.' or lowercase English letters.
- At most 10^4 calls to addWord and search.
"""
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class WordDictionary:
    """
    **LC 211: Design Add and Search Words Data Structure**

    Design a data structure that supports adding new words and finding if a
    string matches any previously added string. The search word can contain
    dots `'.'` where each dot can match any letter.

    * `WordDictionary()` — Initializes the object.
    * `addWord(word)` — Adds `word` to the data structure.
    * `search(word)` — Returns `true` if any string matches `word`.
      A `'.'` matches any single character.

    Example 1:
    ```text
    Input:  ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
            [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
    Output: [null,null,null,null,false,true,true,true]
    ```

    **Constraints:**
    * `1 <= word.length <= 25`
    * `word` in `addWord` consists of lowercase English letters
    * `word` in `search` consists of `'.'` or lowercase English letters
    * At most `10^4` calls to `addWord` and `search`
    """

    def __init__(self):
        # O(1)
        pass

    def addWord(self, word: str) -> None:
        # Standard trie insert: create nodes as needed, mark end_of_word
        # O(m) where m = len(word)
        pass

    def search(self, word: str) -> bool:
        # DFS through trie; '.' matches any child node (try all branches)
        # Regular char must match exactly; return True if end_of_word reached
        # O(m * 26^d) where d = number of dots, worst case O(m * 26^m)
        pass


if __name__ == "__main__":
    wd = WordDictionary()
    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")
    print(wd.search("pad"))   # Expected: False
    print(wd.search("bad"))   # Expected: True
    print(wd.search(".ad"))   # Expected: True
    print(wd.search("b.."))   # Expected: True
Extra Characters In A String ▼ expand 
from typing import List


class Solution:
    """
    **LC 2707: Extra Characters in a String**

    You are given a string `s` and a dictionary of words `dictionary`. Break `s`
    into one or more non-overlapping substrings such that each substring is in
    the dictionary. Some characters may be left over — return the **minimum**
    number of extra characters left over.

    Example 1:
    ```text
    Input:  s = "leetscode", dictionary = ["leet","code","leetcode"]
    Output: 1
    Explanation: Break into "leet" + "s" + "code". Extra = 1 character "s".
    ```

    Example 2:
    ```text
    Input:  s = "sayhelloworld", dictionary = ["hello","world"]
    Output: 3
    Explanation: Break into "say" + "hello" + "world". Extra = 3 characters "say".
    ```

    **Constraints:**
    * `1 <= s.length <= 50`
    * `1 <= dictionary.length <= 50`
    * `1 <= dictionary[i].length <= 50`
    * `dictionary[i]` and `s` consist of only lowercase English letters
    """

    def minExtraChar_dp(self, s: str, dictionary: List[str]) -> int:
        # O(n^2 * m) — DP with hash set lookup
        pass

    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        # DP: dp[i] = min extra chars in s[:i]
        # For each position, try all dictionary words ending at i; take minimum
        # O(n^2 * m) — DP with Trie for prefix matching
        pass


if __name__ == "__main__":
    sol = Solution()

    # Example 1: expected 1
    print(sol.minExtraChar("leetscode", ["leet", "code", "leetcode"]))

    # Example 2: expected 3
    print(sol.minExtraChar("sayhelloworld", ["hello", "world"]))
Implement Trie Prefix Tree ▼ expand 
"""
# 208: Implement Trie (Prefix Tree)

Implement a trie (prefix tree) supporting insertion, exact-match search, and
prefix search: `insert(word)`, `search(word)`, and `startsWith(prefix)`.

## Examples
```text
Input:  insert("apple"); search("apple"); search("app")
        startsWith("app"); insert("app"); search("app")
Output: True; False; True; True
```

## Constraints
- 1 <= word.length, prefix.length <= 2000
- word and prefix consist only of lowercase English letters.
- At most 3 * 10^4 calls in total.
"""
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class Trie:
    """
    **LC 208: Implement Trie (Prefix Tree)**

    A trie (prefix tree) is a tree data structure used to efficiently store
    and retrieve keys in a dataset of strings. Implement the `Trie` class:

    * `Trie()` — Initializes the trie object.
    * `insert(word)` — Inserts the string `word` into the trie.
    * `search(word)` — Returns `true` if `word` is in the trie (exact match).
    * `startsWith(prefix)` — Returns `true` if any previously inserted string
      has the prefix `prefix`.

    Example 1:
    ```text
    Input:  ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
            [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    Output: [null, null, true, false, true, null, true]
    ```

    **Constraints:**
    * `1 <= word.length, prefix.length <= 2000`
    * `word` and `prefix` consist only of lowercase English letters
    * At most `3 * 10^4` calls in total
    """

    def __init__(self):
        # O(1)
        pass

    def insert(self, word: str) -> None:
        # Walk character by character; create new TrieNode if path doesn't exist
        # Mark end_of_word on the final node
        # O(m) where m = len(word)
        pass

    def search(self, word: str) -> bool:
        # Walk the trie; return True only if path exists AND end_of_word is set
        # O(m)
        pass

    def startsWith(self, prefix: str) -> bool:
        # Walk the trie; return True if the prefix path exists (end_of_word irrelevant)
        # O(m)
        pass


if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))       # Expected: True
    print(trie.search("app"))         # Expected: False
    print(trie.startsWith("app"))     # Expected: True
    trie.insert("app")
    print(trie.search("app"))         # Expected: True
Word Search Ii ▼ expand 
"""
# 212: Word Search II

Given an `m x n` board of characters and a list of `words`, return all words
that can be constructed from sequentially adjacent (horizontal/vertical) cells,
using each cell at most once per word.

## Examples
```text
Input:  board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
        words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Input:  board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

## Constraints
- m == board.length, n == board[i].length
- 1 <= m, n <= 12
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- All strings in words are unique.
"""
from typing import List


class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


class Solution:
    """
    **LC 212: Word Search II**

    Given an `m x n` board of characters and a list of strings `words`, return
    all words on the board. Each word must be constructed from letters of
    sequentially adjacent cells (horizontally or vertically neighboring). The
    same cell may not be used more than once in a word.

    Example 1:
    ```text
    Input:  board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
            words = ["oath","pea","eat","rain"]
    Output: ["eat","oath"]
    ```

    Example 2:
    ```text
    Input:  board = [["a","b"],["c","d"]]
            words = ["abcb"]
    Output: []
    ```

    **Constraints:**
    * `m == board.length`, `n == board[i].length`
    * `1 <= m, n <= 12`
    * `board[i][j]` is a lowercase English letter
    * `1 <= words.length <= 3 * 10^4`
    * `1 <= words[i].length <= 10`
    * All strings in `words` are unique
    """

    def findWords_brute(self, board: List[List[str]], words: List[str]) -> List[str]:
        # O(w * m * n * 4^L) — DFS per word independently
        pass

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build a trie from all words for efficient prefix pruning
        # DFS from each cell; prune when current path is not a trie prefix
        # When a word is found in trie, add to result and remove from trie to avoid duplicates
        # O(m * n * 4^L) — Trie + backtracking DFS (prune branches)
        pass


if __name__ == "__main__":
    sol = Solution()

    # Example 1: expected ["eat", "oath"]
    board1 = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
    print(sol.findWords(board1, ["oath","pea","eat","rain"]))

    # Example 2: expected []
    board2 = [["a","b"],["c","d"]]
    print(sol.findWords(board2, ["abcb"]))

Trie — Insert & Search

Prefix tree for O(m) string operations. * = end of word.

root
  • a
    • p
      • p *
        • l
          • e *
      • t *
  • b
    • a
      • l
        • l *
      • t *
Trie preloaded with: apple, app, apt, bat, ball