Problems

Practice these carefully selected trie problems to reinforce your understanding. Before starting, review the Code Templates for reusable implementations.

Easy

1. Implement Trie (Prefix Tree)

Brief: Implement a trie with insert, search, and startsWith methods.
Why this pattern?: This is the foundational trie problem - master it first.
Key Insight: Use a map for children and a boolean flag for word endings.

  flowchart TD
    R((root)) --> A((a))
    A --> P1((p))
    P1 --> P2(("p*"))
    P2 --> L((l))
    L --> E(("e*"))

    style P2 fill:#c8e6c9
    style E fill:#c8e6c9

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() { this.root = new TrieNode(); }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    search(word) {
        const node = this._traverse(word);
        return node !== null && node.isEndOfWord;
    }

    startsWith(prefix) {
        return this._traverse(prefix) !== null;
    }

    _traverse(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) return null;
            node = node.children.get(char);
        }
        return node;
    }
}

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

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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._traverse(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._traverse(prefix) is not None

    def _traverse(self, word: str):
        node = self.root
        for char in word:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = traverse(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return traverse(prefix) != null;
    }

    private TrieNode traverse(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return null;
            node = node.children.get(ch);
        }
        return node;
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

class Trie {
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    TrieNode* root = new TrieNode();

    TrieNode* traverse(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) return nullptr;
            node = node->children[ch];
        }
        return node;
    }

public:
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = traverse(word);
        return node && node->isEnd;
    }

    bool startsWith(string prefix) {
        return traverse(prefix) != nullptr;
    }
};

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct { root *TrieNode }

func Constructor() Trie {
    return Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.traverse(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.traverse(prefix) != nil
}

func (t *Trie) traverse(word string) *TrieNode {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil { return nil }
        node = node.children[ch]
    }
    return node
}

class TrieNode
  attr_accessor :children, :is_end
  def initialize
    @children, @is_end = {}, false
  end
end

class Trie
  def initialize
    @root = TrieNode.new
  end

  def insert(word)
    node = @root
    word.each_char do |ch|
      node.children[ch] ||= TrieNode.new
      node = node.children[ch]
    end
    node.is_end = true
  end

  def search(word)
    node = traverse(word)
    !node.nil? && node.is_end
  end

  def starts_with(prefix)
    !traverse(prefix).nil?
  end

  private
  def traverse(word)
    node = @root
    word.each_char { |ch| return nil unless node.children[ch]; node = node.children[ch] }
    node
  end
end

Complexity: Time

O(M)

| Space

O(M)

where M is word length

Medium

2. Design Add and Search Words Data Structure

Brief: Design a data structure that supports adding words and searching with wildcards (. matches any character).
Why this pattern?: Extends basic trie with DFS for wildcard matching.
Key Insight: When encountering ., recursively try all children.

class WordDictionary {
    constructor() { this.root = new TrieNode(); }

    addWord(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    search(word) {
        return this._dfs(word, 0, this.root);
    }

    _dfs(word, index, node) {
        if (index === word.length) return node.isEndOfWord;

        const char = word[index];
        if (char === '.') {
            for (const child of node.children.values()) {
                if (this._dfs(word, index + 1, child)) return true;
            }
            return false;
        } else {
            if (!node.children.has(char)) return false;
            return this._dfs(word, index + 1, node.children.get(char));
        }
    }
}

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

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        return self._dfs(word, 0, self.root)

    def _dfs(self, word: str, index: int, node) -> bool:
        if index == len(word):
            return node.is_end

        char = word[index]
        if char == '.':
            for child in node.children.values():
                if self._dfs(word, index + 1, child):
                    return True
            return False
        else:
            if char not in node.children:
                return False
            return self._dfs(word, index + 1, node.children[char])

class WordDictionary {
    private TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int index, TrieNode node) {
        if (index == word.length()) return node.isEnd;

        char ch = word.charAt(index);
        if (ch == '.') {
            for (TrieNode child : node.children.values()) {
                if (dfs(word, index + 1, child)) return true;
            }
            return false;
        } else {
            if (!node.children.containsKey(ch)) return false;
            return dfs(word, index + 1, node.children.get(ch));
        }
    }
}

class WordDictionary {
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    TrieNode* root = new TrieNode();

    bool dfs(const string& word, int index, TrieNode* node) {
        if (index == word.size()) return node->isEnd;

        char ch = word[index];
        if (ch == '.') {
            for (auto& [c, child] : node->children) {
                if (dfs(word, index + 1, child)) return true;
            }
            return false;
        } else {
            if (!node->children.count(ch)) return false;
            return dfs(word, index + 1, node->children[ch]);
        }
    }

public:
    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        return dfs(word, 0, root);
    }
};

type WordDictionary struct {
    root *TrieNode
}

func Constructor() WordDictionary {
    return WordDictionary{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (wd *WordDictionary) AddWord(word string) {
    node := wd.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (wd *WordDictionary) Search(word string) bool {
    return wd.dfs(word, 0, wd.root)
}

func (wd *WordDictionary) dfs(word string, index int, node *TrieNode) bool {
    if index == len(word) { return node.isEnd }

    ch := rune(word[index])
    if ch == '.' {
        for _, child := range node.children {
            if wd.dfs(word, index+1, child) { return true }
        }
        return false
    }
    if node.children[ch] == nil { return false }
    return wd.dfs(word, index+1, node.children[ch])
}

class WordDictionary
  def initialize
    @root = TrieNode.new
  end

  def add_word(word)
    node = @root
    word.each_char do |ch|
      node.children[ch] ||= TrieNode.new
      node = node.children[ch]
    end
    node.is_end = true
  end

  def search(word)
    dfs(word, 0, @root)
  end

  private
  def dfs(word, index, node)
    return node.is_end if index == word.length

    ch = word[index]
    if ch == '.'
      node.children.values.each do |child|
        return true if dfs(word, index + 1, child)
      end
      false
    else
      return false unless node.children[ch]
      dfs(word, index + 1, node.children[ch])
    end
  end
end

Complexity: Time

O(M)

for add,

O(26^M)

worst case for search | Space

O(M)

3. Replace Words

Brief: Replace words in a sentence with their shortest root from a dictionary.
Why this pattern?: Trie finds shortest matching prefix efficiently.
Key Insight: For each word, traverse trie until you hit an end marker.

function replaceWords(dictionary, sentence) {
    const root = new TrieNode();

    // Build trie from dictionary
    for (const word of dictionary) {
        let node = root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    // Replace words
    return sentence.split(' ').map(word => {
        let node = root;
        let prefix = '';
        for (const char of word) {
            if (!node.children.has(char) || node.isEndOfWord) break;
            node = node.children.get(char);
            prefix += char;
        }
        return node.isEndOfWord ? prefix : word;
    }).join(' ');
}

def replaceWords(dictionary: list, sentence: str) -> str:
    root = TrieNode()

    # Build trie from dictionary
    for word in dictionary:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    # Replace words
    result = []
    for word in sentence.split():
        node = root
        prefix = ''
        for char in word:
            if char not in node.children or node.is_end:
                break
            node = node.children[char]
            prefix += char
        result.append(prefix if node.is_end else word)
    return ' '.join(result)

public String replaceWords(List<String> dictionary, String sentence) {
    TrieNode root = new TrieNode();

    // Build trie
    for (String word : dictionary) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    // Replace words
    StringBuilder result = new StringBuilder();
    for (String word : sentence.split(" ")) {
        if (result.length() > 0) result.append(" ");
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch) || node.isEnd) break;
            node = node.children.get(ch);
            prefix.append(ch);
        }
        result.append(node.isEnd ? prefix : word);
    }
    return result.toString();
}

string replaceWords(vector<string>& dictionary, string sentence) {
    TrieNode* root = new TrieNode();

    // Build trie
    for (const string& word : dictionary) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    // Replace words
    stringstream ss(sentence);
    string word, result;
    while (ss >> word) {
        if (!result.empty()) result += " ";
        TrieNode* node = root;
        string prefix;
        for (char ch : word) {
            if (!node->children.count(ch) || node->isEnd) break;
            node = node->children[ch];
            prefix += ch;
        }
        result += node->isEnd ? prefix : word;
    }
    return result;
}

func replaceWords(dictionary []string, sentence string) string {
    root := &TrieNode{children: make(map[rune]*TrieNode)}

    // Build trie
    for _, word := range dictionary {
        node := root
        for _, ch := range word {
            if node.children[ch] == nil {
                node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
            }
            node = node.children[ch]
        }
        node.isEnd = true
    }

    // Replace words
    words := strings.Split(sentence, " ")
    for i, word := range words {
        node := root
        prefix := ""
        for _, ch := range word {
            if node.children[ch] == nil || node.isEnd { break }
            node = node.children[ch]
            prefix += string(ch)
        }
        if node.isEnd { words[i] = prefix }
    }
    return strings.Join(words, " ")
}

def replace_words(dictionary, sentence)
  root = TrieNode.new

  # Build trie
  dictionary.each do |word|
    node = root
    word.each_char do |ch|
      node.children[ch] ||= TrieNode.new
      node = node.children[ch]
    end
    node.is_end = true
  end

  # Replace words
  sentence.split.map do |word|
    node = root
    prefix = ''
    word.each_char do |ch|
      break if !node.children[ch] || node.is_end
      node = node.children[ch]
      prefix += ch
    end
    node.is_end ? prefix : word
  end.join(' ')
end

Complexity: Time

O(N*M)

| Space

O(D*L)

where D is dictionary size, L is avg word length

4. Longest Word in Dictionary

Brief: Find the longest word that can be built one character at a time.
Why this pattern?: Trie naturally represents incremental word building.
Key Insight: DFS through trie, only following paths where each node is a word end.

function longestWord(words) {
    const root = new TrieNode();

    // Build trie
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
        node.word = word;
    }

    let result = '';

    function dfs(node) {
        for (const [char, child] of [...node.children.entries()].sort()) {
            if (child.isEndOfWord) {
                if (child.word.length > result.length) {
                    result = child.word;
                }
                dfs(child);
            }
        }
    }

    dfs(root);
    return result;
}

def longestWord(words: list) -> str:
    root = TrieNode()

    # Build trie
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.word = word

    result = ''

    def dfs(node):
        nonlocal result
        for char in sorted(node.children.keys()):
            child = node.children[char]
            if child.is_end:
                if len(child.word) > len(result):
                    result = child.word
                dfs(child)

    dfs(root)
    return result

public String longestWord(String[] words) {
    TrieNode root = new TrieNode();

    for (String word : words) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
        node.word = word;
    }

    String[] result = {""};
    dfs(root, result);
    return result[0];
}

private void dfs(TrieNode node, String[] result) {
    List<Character> keys = new ArrayList<>(node.children.keySet());
    Collections.sort(keys);
    for (char ch : keys) {
        TrieNode child = node.children.get(ch);
        if (child.isEnd) {
            if (child.word.length() > result[0].length()) {
                result[0] = child.word;
            }
            dfs(child, result);
        }
    }
}

string longestWord(vector<string>& words) {
    TrieNode* root = new TrieNode();

    for (const string& word : words) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
        node->word = word;
    }

    string result;
    function<void(TrieNode*)> dfs = [&](TrieNode* node) {
        vector<char> keys;
        for (auto& [ch, _] : node->children) keys.push_back(ch);
        sort(keys.begin(), keys.end());
        for (char ch : keys) {
            TrieNode* child = node->children[ch];
            if (child->isEnd) {
                if (child->word.size() > result.size())
                    result = child->word;
                dfs(child);
            }
        }
    };
    dfs(root);
    return result;
}

func longestWord(words []string) string {
    root := &TrieNode{children: make(map[rune]*TrieNode)}

    for _, word := range words {
        node := root
        for _, ch := range word {
            if node.children[ch] == nil {
                node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
            }
            node = node.children[ch]
        }
        node.isEnd = true
        node.word = word
    }

    result := ""
    var dfs func(*TrieNode)
    dfs = func(node *TrieNode) {
        keys := make([]rune, 0)
        for ch := range node.children { keys = append(keys, ch) }
        sort.Slice(keys, func(i, j int) bool { return keys[i] < keys[j] })
        for _, ch := range keys {
            child := node.children[ch]
            if child.isEnd {
                if len(child.word) > len(result) { result = child.word }
                dfs(child)
            }
        }
    }
    dfs(root)
    return result
}

def longest_word(words)
  root = TrieNode.new

  words.each do |word|
    node = root
    word.each_char do |ch|
      node.children[ch] ||= TrieNode.new
      node = node.children[ch]
    end
    node.is_end = true
    node.word = word
  end

  result = ''
  dfs = ->(node) {
    node.children.keys.sort.each do |ch|
      child = node.children[ch]
      if child.is_end
        result = child.word if child.word.length > result.length
        dfs.call(child)
      end
    end
  }
  dfs.call(root)
  result
end

Complexity: Time

O(N*M)

| Space

O(N*M)

Hard

5. Word Search II

Brief: Find all words from a dictionary that exist in a character grid.
Why this pattern?: Trie enables efficient pruning during grid DFS.
Key Insight: Build trie from words, then DFS from each cell using trie as guide.

function findWords(board, words) {
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children.has(char)) node.children.set(char, new TrieNode());
            node = node.children.get(char);
        }
        node.word = word;
    }

    const result = new Set();
    const rows = board.length, cols = board[0].length;

    function dfs(i, j, node) {
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        const char = board[i][j];
        if (char === '#' || !node.children.has(char)) return;

        const next = node.children.get(char);
        if (next.word) result.add(next.word);

        board[i][j] = '#';
        dfs(i+1, j, next); dfs(i-1, j, next);
        dfs(i, j+1, next); dfs(i, j-1, next);
        board[i][j] = char;
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dfs(i, j, root);
        }
    }
    return [...result];
}

def findWords(board: list, words: list) -> list:
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word

    result = set()
    rows, cols = len(board), len(board[0])

    def dfs(i, j, node):
        if i < 0 or i >= rows or j < 0 or j >= cols:
            return
        char = board[i][j]
        if char == '#' or char not in node.children:
            return

        next_node = node.children[char]
        if next_node.word:
            result.add(next_node.word)

        board[i][j] = '#'
        dfs(i+1, j, next_node); dfs(i-1, j, next_node)
        dfs(i, j+1, next_node); dfs(i, j-1, next_node)
        board[i][j] = char

    for i in range(rows):
        for j in range(cols):
            dfs(i, j, root)
    return list(result)

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    for (String word : words) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.word = word;
    }

    Set<String> result = new HashSet<>();
    int rows = board.length, cols = board[0].length;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dfs(board, i, j, root, result);
        }
    }
    return new ArrayList<>(result);
}

private void dfs(char[][] board, int i, int j, TrieNode node, Set<String> result) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
    char ch = board[i][j];
    if (ch == '#' || !node.children.containsKey(ch)) return;

    TrieNode next = node.children.get(ch);
    if (next.word != null) result.add(next.word);

    board[i][j] = '#';
    dfs(board, i+1, j, next, result); dfs(board, i-1, j, next, result);
    dfs(board, i, j+1, next, result); dfs(board, i, j-1, next, result);
    board[i][j] = ch;
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    TrieNode* root = new TrieNode();
    for (const string& word : words) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->word = word;
    }

    set<string> result;
    int rows = board.size(), cols = board[0].size();

    function<void(int, int, TrieNode*)> dfs = [&](int i, int j, TrieNode* node) {
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        char ch = board[i][j];
        if (ch == '#' || !node->children.count(ch)) return;

        TrieNode* next = node->children[ch];
        if (!next->word.empty()) result.insert(next->word);

        board[i][j] = '#';
        dfs(i+1, j, next); dfs(i-1, j, next);
        dfs(i, j+1, next); dfs(i, j-1, next);
        board[i][j] = ch;
    };

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            dfs(i, j, root);
    return vector<string>(result.begin(), result.end());
}

func findWords(board [][]byte, words []string) []string {
    root := &TrieNode{children: make(map[rune]*TrieNode)}
    for _, word := range words {
        node := root
        for _, ch := range word {
            if node.children[ch] == nil {
                node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
            }
            node = node.children[ch]
        }
        node.word = word
    }

    result := make(map[string]bool)
    rows, cols := len(board), len(board[0])

    var dfs func(int, int, *TrieNode)
    dfs = func(i, j int, node *TrieNode) {
        if i < 0 || i >= rows || j < 0 || j >= cols { return }
        ch := rune(board[i][j])
        if ch == '#' || node.children[ch] == nil { return }

        next := node.children[ch]
        if next.word != "" { result[next.word] = true }

        board[i][j] = '#'
        dfs(i+1, j, next); dfs(i-1, j, next)
        dfs(i, j+1, next); dfs(i, j-1, next)
        board[i][j] = byte(ch)
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ { dfs(i, j, root) }
    }

    res := make([]string, 0)
    for w := range result { res = append(res, w) }
    return res
}

def find_words(board, words)
  root = TrieNode.new
  words.each do |word|
    node = root
    word.each_char do |ch|
      node.children[ch] ||= TrieNode.new
      node = node.children[ch]
    end
    node.word = word
  end

  result = Set.new
  rows, cols = board.length, board[0].length

  dfs = ->(i, j, node) {
    return if i < 0 || i >= rows || j < 0 || j >= cols
    ch = board[i][j]
    return if ch == '#' || !node.children[ch]

    next_node = node.children[ch]
    result.add(next_node.word) if next_node.word

    board[i][j] = '#'
    dfs.call(i+1, j, next_node); dfs.call(i-1, j, next_node)
    dfs.call(i, j+1, next_node); dfs.call(i, j-1, next_node)
    board[i][j] = ch
  }

  (0...rows).each { |i| (0...cols).each { |j| dfs.call(i, j, root) } }
  result.to_a
end

Complexity: Time

O(M*N*4^L)

| Space

O(W*L)

where W is word count, L is max length

Recommended Study Order

Start with Implement Trie to understand the core data structure
Move to Add and Search Words to learn wildcard handling with DFS
Try Replace Words for practical prefix matching
Tackle Longest Word for DFS traversal patterns
Challenge yourself with Word Search II for advanced grid + trie combination

Study Tip: For each problem, first implement the basic trie, then think about what additional information each node needs to store.