Chương 23 - Trie

Trie (prefix tree) là cây mà mỗi node đại diện cho một ký tự, mỗi đường đi từ root đến node = 1 prefix. Trie giải gọn các bài “tìm word có prefix X”, “search với wildcard”, “longest common prefix nhiều query”. Pattern Bitmask + Trie sẽ ở Chương 41.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Trie = mỗi node = 1 ký tự, đường đi root → node = 1 prefix.
  • Phân biệt dict[str, Node] (Unicode) vs array 26 (a-z, nhanh hơn).
  • Reverse trick: build trie trên word đảo ngược cho suffix matching.
  • Prune nhánh sau khi tìm thấy để tránh duplicate (Word Search II).

Khi nào dùng pattern này?

  • Đa truy vấn về prefix trên cùng tập word.
  • Bài có wildcard . hoặc fuzzy search.
  • Lookup từ dictionary trong bài board / matrix (Word Search II).
  • Truy vấn XOR cực đại - biểu diễn số dưới dạng binary trie.

Template code 

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


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

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

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

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

    def _find(self, s: str) -> "TrieNode | None":
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Bài tự luyện cuối chương

  • LC 421 - Maximum XOR of Two Numbers (Chương 41)
  • LC 588 - Design In-Memory File System
  • LC 642 - Design Search Autocomplete System
  • LC 745 - Prefix and Suffix Search

23.1 Implement Trie (LC 208)

Đề bài

Cài đặt class Trie với 3 method: insert, search, startsWith. Yêu cầu mỗi op O(length(word)).

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
  args = [[],     ["apple"], ["apple"], ["app"], ["app"],      ["app"],  ["app"]]

Output: [null, null, true, false, true, null, true]

Giải thích:
  Trie()                  → khởi tạo, return null
  insert("apple")         → null
  search("apple")         → true
  search("app")           → false  (chưa insert "app" riêng)
  startsWith("app")       → true   (vẫn là prefix của "apple")
  insert("app")           → null
  search("app")           → true

Ràng buộc

  • 1 <= len(word), len(prefix) <= 2000
  • Word chỉ chứa chữ thường
  • Tối đa 3·10^4 op

Clarifying questions

  • Insert empty string? → Cho phép; search(““) trả True.
  • Case-sensitive? → Theo đề: chỉ chữ thường.

Hướng tiếp cận

Trie = cây mà mỗi node là 1 ký tự, đường đi root → node là 1 prefix. Insert: walk theo ký tự, tạo node mới khi cần, mark is_end ở node cuối. Search/StartsWith: walk theo ký tự, return False nếu thiếu node.

Code Python 3 

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


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

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

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

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

    def _find(self, s: str) -> "TrieNode | None":
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Phân tích độ phức tạp

  • Insert / Search / StartsWith: O(L) với L = độ dài từ.
  • Bộ nhớ: O(N · L) cho N từ tổng dài.

Bình luận

  • Array-based (children: TrieNode[26]) nhanh hơn dict[str, TrieNode] với bảng chữ nhỏ, nhưng tốn space hơn.
  • __slots__ giảm overhead khi có nhiều node.

Bài tự luyện liên quan

  • LC 211 - Add and Search Word.
  • LC 1268 - Search Suggestions System.

23.2 Add and Search Word (LC 211)

Đề bài

Cài đặt class với addWord(word) và search(word). search cho phép . thay cho bất kỳ ký tự nào.

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"]
  args = [[],               ["bad"],   ["dad"],   ["mad"],   ["pad"],  ["bad"],  [".ad"],  ["b.."]]

Output: [null, null, null, null, false, true, true, true]

Giải thích:
  WordDictionary()      → null
  addWord("bad")        → null
  addWord("dad")        → null
  addWord("mad")        → null
  search("pad")         → false   ("pad" chưa từng add)
  search("bad")         → true
  search(".ad")         → true    (`.` match 1 char bất kỳ → khớp "bad", "dad", "mad")
  search("b..")         → true    (khớp "bad")

Ràng buộc

  • 1 <= len(word) <= 25
  • Tối đa 10^4 op

Clarifying questions

  • Wildcard tối đa bao nhiêu? → Theo LC: 2 wildcard.
  • _addWord(““)?_ → Cho phép; search(”“) trả True nếu có addWord(”“).

Hướng tiếp cận

addWord y hệt Trie thường. search cần DFS đệ quy khi gặp .: thử tất cả children.

Code Python 3 

class WordDictionary:
    def __init__(self):
        self.root: dict = {}

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True       # marker end

    def search(self, word: str) -> bool:
        def dfs(node: dict, i: int) -> bool:
            if i == len(word):
                return '$' in node
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1)
                           for k, child in node.items() if k != '$')
            if ch not in node:
                return False
            return dfs(node[ch], i + 1)

        return dfs(self.root, 0)

Phân tích độ phức tạp

  • addWord: O(L).
  • search: O(L) không wildcard; O(26^L) worst với toàn ..

Bình luận

  • Dùng dict[str] thay vì class - code ngắn hơn, dễ quan sát khi in ra để gỡ lỗi. Dùng marker $ để đánh dấu kết thúc word (thay cho thuộc tính is_end).

Bài tự luyện liên quan

  • LC 720 - Longest Word in Dictionary (bài 23.4).

23.3 Word Search II (LC 212)

Đề bài

Cho ma trận board và mảng words. Trả về tất cả word xuất hiện trên board (qua đường đi 4 hướng, không thăm 1 ô 2 lần).

Ví dụ 

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

Output: ["oath", "eat"]   (thứ tự trong output có thể tuỳ ý)

Ràng buộc

  • 1 <= m, n <= 12
  • 1 <= len(words) <= 3·10^4

Clarifying questions

  • Word trùng nhau trong words? → Vẫn coi như 1 lần xuất hiện.
  • Board rỗng? → Trả [].

Hướng tiếp cận

Brute force: với mỗi word, DFS từ mỗi ô → O(W · m · n · 4^L). TLE.

Trie + DFS - O(m · n · 4^L) (không phụ thuộc số word).

Build Trie từ words. DFS từ mỗi ô, đồng hành với một con trỏ trên Trie. Khi gặp node có is_end → thêm word vào kết quả. Sau khi đã ghi nhận 1 word, nên xoá word đó khỏi Trie (đặt is_end = None) để tránh tìm trùng.

Code Python 3 

from typing import List

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # 1. Build Trie.
        root: dict = {}
        for w in words:
            node = root
            for ch in w:
                node = node.setdefault(ch, {})
            node['$'] = w

        rows, cols = len(board), len(board[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        result: list[str] = []

        def dfs(r: int, c: int, node: dict) -> None:
            ch = board[r][c]
            if ch not in node:
                return
            nxt = node[ch]
            if '$' in nxt:
                result.append(nxt['$'])
                del nxt['$']           # tránh add trùng
            board[r][c] = '#'
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    dfs(nr, nc, nxt)
            board[r][c] = ch
            if not nxt:
                del node[ch]            # prune

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)
        return result

Phân tích độ phức tạp

  • Thời gian: O(m · n · 4^L) worst.
  • Bộ nhớ: O(N · L) cho Trie.

Bình luận

  • Prune Trie khi node trống - giảm work cho các ô sau.
  • Mark board = đổi tạm # rồi restore (visited).
  • Bài rất nổi tiếng ở Big Tech - hỏi thuần Trie + DFS pattern.

Bài tự luyện liên quan

  • LC 79 - Word Search (single word, không Trie).
  • LC 1268 - Search Suggestions System.

23.4 Longest Word in Dictionary (LC 720)

Đề bài

Cho mảng words. Tìm word dài nhất mà mọi prefix của nó cũng có trong mảng. Nếu hoà, lấy word lex smallest.

Ví dụ 

Input:  words = ["w","wo","wor","worl","world"]
Output: "world"   (mọi prefix lồng nhau đều có trong words; có nhiều thì lấy lex nhỏ nhất)

Input:  words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
("apple" và "apply" đều có toàn bộ prefix lồng nhau trong words;
 "apple" < "apply" theo thứ tự lex → chọn "apple")

Ràng buộc

  • 1 <= len(words) <= 1000
  • 1 <= len(words[i]) <= 30

Clarifying questions

  • Words rỗng? → Trả ““.
  • Tie? → Lex smallest.

Hướng tiếp cận

Cách 1 - Sort + set, O(N · L log N). Sort words. Duy trì valid set. Đi qua từng word: nếu mọi prefix của nó đã trong valid (chỉ cần check prefix length-1), thêm vào valid.

Cách 2 - Trie + BFS/DFS. Build Trie. DFS preorder, ưu tiên is_end. Chỉ đi sâu nếu is_end true.

Cách 1 ngắn gọn hơn cho bài này.

Code Python 3 

from typing import List

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()                          # lex
        valid: set[str] = {""}
        best = ""
        for w in words:
            if w[:-1] in valid:
                valid.add(w)
                if len(w) > len(best):
                    best = w
        return best

Phân tích độ phức tạp

  • Thời gian: O(Σ L · log N). Bộ nhớ: O(Σ L).

Bình luận

  • Tinh tế: sort lex trước → khi gặp word dài hơn cùng prefix, ta giữ cái đầu tiên (lex smaller).

Bài tự luyện liên quan

  • LC 1268 - Search Suggestions System.

23.5 Replace Words (LC 648)

Đề bài

Cho dictionary (các “root”) và câu sentence. Với mỗi từ trong sentence, thay nó bằng root ngắn nhất trong dictionary là prefix của nó. Nếu không có root nào → giữ từ.

Ví dụ 

Input:  dictionary = ["cat","bat","rat"]
        sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Ràng buộc

  • 1 <= len(dictionary) <= 1000
  • 1 <= len(roots[i]) <= 100
  • 1 <= len(sentence) <= 10^6

Clarifying questions

  • Multiple root match? → Lấy root ngắn nhất.
  • Sentence rỗng? → Trả ““.

Hướng tiếp cận

Trie. Insert tất cả root. Với mỗi word trong sentence, duyệt qua Trie: khi gặp is_end đầu tiên → thay bằng prefix tới đó.

Code Python 3 

from typing import List

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root: dict = {}
        for w in dictionary:
            node = root
            for ch in w:
                node = node.setdefault(ch, {})
            node['$'] = True

        def replace(word: str) -> str:
            node = root
            prefix = []
            for ch in word:
                if '$' in node:
                    return ''.join(prefix)
                if ch not in node:
                    return word
                prefix.append(ch)
                node = node[ch]
            return ''.join(prefix) if '$' in node else word

        return ' '.join(replace(w) for w in sentence.split())

Phân tích độ phức tạp

  • Thời gian: O(N_dict · L + N_sent · L). Bộ nhớ: O(N_dict · L).

Bình luận

  • Pattern Trie traversal với early exit ở is_end - kinh điển.

Bài tự luyện liên quan

  • LC 1268 - Search Suggestions System.

23.6 Stream of Characters (LC 1032)

Đề bài

Thiết kế class StreamChecker với constructor lấy danh sách words. Method query(letter) trả về True nếu suffix của stream hiện tại match một word trong list.

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["StreamChecker", "query", "query", "query", "query", "query", "query"]
  args = [[["cd","f","kl"]], ["a"],  ["b"],   ["c"],   ["d"],   ["e"],   ["f"]]

Output: [null, false, false, false, true, false, true]

Giải thích:
  StreamChecker(["cd","f","kl"])
  query('a')  → false  (stream = "a")
  query('b')  → false  (stream = "ab")
  query('c')  → false  (stream = "abc")
  query('d')  → true   (suffix "cd" của stream "abcd" match)
  query('e')  → false
  query('f')  → true   (suffix "f" match)

Ràng buộc

  • 1 <= len(words) <= 2000
  • 1 <= len(words[i]) <= 200

Clarifying questions

  • Word trong list có thể rỗng không? → Theo đề: không.

Hướng tiếp cận

Insight: suffix khó tìm theo prefix Trie. Reverse trick - build Trie trên các word đảo ngược. Stream cũng đảo (mới nhất đầu): kiểm tra prefix của reversed-stream match Trie.

Implementation: giữ buffer các ký tự đã query. Mỗi query, walk Trie với buffer từ cuối lên đầu (= word đảo).

Code Python 3 

from typing import List

class StreamChecker:
    def __init__(self, words: List[str]):
        self.root: dict = {}
        for w in words:
            node = self.root
            for ch in reversed(w):
                node = node.setdefault(ch, {})
            node['$'] = True
        self.buf: list[str] = []

    def query(self, letter: str) -> bool:
        self.buf.append(letter)
        node = self.root
        for ch in reversed(self.buf):
            if '$' in node:
                return True
            if ch not in node:
                return False
            node = node[ch]
        return '$' in node

Phân tích độ phức tạp

  • Init: O(Σ L).
  • Query: O(max_word_length).

Bình luận

  • Bẫy: không giới hạn buf → khi stream rất dài, mỗi query vẫn chỉ đi sâu ≤ max_word_length (sẽ break sớm khi không match).
  • Reverse trick là chìa khoá - chuyển bài suffix về bài prefix.

Bài tự luyện liên quan

  • LC 745 - Prefix and Suffix Search.

Tóm tắt chương & Quyết định

Trie design tradeoff

Tiêu chí Dict children {ch: TrieNode} Array [26]
Bộ nhớ Nhỏ khi sparse Lớn nhưng đều
Truy cập O(1) hash O(1) index
Hỗ trợ Unicode ✅ ❌ (chỉ 26 chữ)
Code Pythonic, ngắn Nhanh hơn ở C++/Java

Word Search II (LC 212) - pruning

  • Trie chứa tất cả từ trong words. DFS từ mỗi cell với pointer trie.
  • Cắt nhánh: nếu char hiện tại không có trong children → return ngay.
  • Tránh duplicate: sau khi tìm được word, set node.word = None (xóa khỏi trie) để không add 2 lần.

Stream of Characters (LC 1032) - reverse trie

  • Stream c_0 c_1 c_2 .... Hỏi sau mỗi char, có hậu tố nào trùng word không.
  • Build trie của các word đảo ngược. Sau khi nhận c_i, đi từ c_i, c_{i-1}, ... ngược lên - đây là prefix trong trie đảo.

Replace Words (LC 648) - shortest root

Khi đi xuống trie, dừng ngay tại node terminal đầu tiên - đó là root ngắn nhất thay được. Đi tiếp chỉ ra root dài hơn (vô ích).