Buổi 06 — String Matching & Trie

Navigation

← 05-Divide-and-Conquer | → 07-Union-Find Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

1. Analogy & Context

Rolling Hash — Máy quét dấu vân tay di động

Hình dung cảnh sát dùng máy quét dấu vân tay di động để tìm nghi phạm trong đám đông. Thay vì dừng lại toàn bộ đám đông để quét từng người từ đầu, máy trượt từng bước một: bỏ người đầu tiên ra, thêm người mới vào cuối — và tính lại fingerprint trong O(1). Đó chính là Rolling Hash.

Trong string matching, pattern là dấu vân tay nghi phạm, text là đám đông. Brute force = O(NM). Rolling Hash (Rabin-Karp) = O(N+M) average.

Trie — Cây autocomplete của thanh tìm kiếm Google

Khi bạn gõ “pre” vào Google, nó gợi ý “prefix”, “preview”, “previous” ngay lập tức. Làm sao? Trie — một cây mà mỗi cạnh là một ký tự. Tất cả các từ bắt đầu bằng “pre” đều chia sẻ cùng nhánh cây. Không cần duyệt toàn bộ dictionary — chỉ đi theo nhánh “p → r → e” là xong.

Khi nào dùng Trie vs HashMap?

Trie: prefix queries, autocomplete, word search trên board với nhiều từ
HashMap: exact match nhanh hơn, ít memory hơn khi không cần prefix
Trie beats HashMap khi: cần startsWith, cần duyệt tất cả từ có chung prefix

2. The FAANG Standard

Tại sao FAANG hỏi Trie & String Matching?

Google: Search autocomplete, spell checker, IP routing (longest prefix match)

Amazon: Product search, catalog prefix lookup

Meta: Username availability, friend name search

Microsoft: IDE autocomplete (IntelliSense)

Ba thuật toán string matching quan trọng:

Thuật toán	Time	Space	Đặc điểm
Brute Force	$O (NM)$	$O (1)$	Đơn giản, chậm
Rabin-Karp (Rolling Hash)	$O (N + M)$ avg, $O (NM)$ worst	$O (1)$	Tốt cho nhiều pattern
KMP	$O (N + M)$ guaranteed	$O (M)$	Dùng failure function
Trie + DFS	$O (N \cdot L)$	$O (TR I E_S I ZE)$	Multi-pattern search trong board

Rule of thumb cho interview

1 pattern trong text → KMP hoặc Rabin-Karp

Nhiều pattern trong board/text → Trie + DFS

Prefix queries → Trie

Repeated substrings → Rolling Hash (sliding window on hash)

3. Visual Thinking (Mermaid)

3.1 Trie cho [“apple”, “app”, “apply”, “apt”]

graph TD
    ROOT((root)) --> A((a))
    A --> AP((p))
    AP --> APP((p))
    APP --> APPE((l))
    APPE --> APPPL((e ✓))
    APP --> APPEND((" ✓ app"))
    AP --> APT((t ✓))
    APP --> APPL2((l))
    APPL2 --> APPLY((y ✓))

    style APPPL fill:#4CAF50,color:#fff
    style APPEND fill:#4CAF50,color:#fff
    style APT fill:#4CAF50,color:#fff
    style APPLY fill:#4CAF50,color:#fff

Nút có dấu ✓ = isEnd = true. Nút “app” vừa là prefix vừa là từ hoàn chỉnh.

3.2 Rolling Hash — Sliding Window

sequenceDiagram
    participant T as Text: "abcde"
    participant H as Hash Window (size 3)

    T->>H: Window "abc" → hash = hash("abc")
    Note over H: hash = (a×B² + b×B + c) % MOD
    T->>H: Slide: remove 'a', add 'd'
    Note over H: hash = (hash - a×B²) × B + d) % MOD
    T->>H: Window "bcd" → O(1) update!
    T->>H: Slide: remove 'b', add 'e'
    T->>H: Window "cde" → O(1) update!

3.3 KMP Failure Function

graph LR
    subgraph Pattern: "ABABC"
        P0[A,0] --> P1[B,0] --> P2[A,1] --> P3[B,2] --> P4[C,0]
    end
    Note["failure[i] = length of longest proper prefix<br/>that is also a suffix at position i"]

4. TypeScript Template

4.1 TrieNode & Trie — Core Implementation

class TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;
 
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}
 
class Trie {
  private root: TrieNode;
 
  constructor() {
    this.root = new TrieNode();
  }
 
  // O(L) — L = word length
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }
 
  // O(L)
  search(word: string): boolean {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return node.isEnd; // IMPORTANT: check isEnd, not just node exists
  }
 
  // O(L)
  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return true; // don't check isEnd — any node counts
  }
}

4.2 Trie với Wildcard Search (’.‘)

// LeetCode #211 — Design Add and Search Words Data Structure
class WordDictionary {
  private root: TrieNode;
 
  constructor() {
    this.root = new TrieNode();
  }
 
  addWord(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }
 
  search(word: string): boolean {
    return this.dfs(this.root, word, 0);
  }
 
  private dfs(node: TrieNode, word: string, i: number): boolean {
    if (i === word.length) return node.isEnd;
 
    const ch = word[i];
    if (ch === '.') {
      // Try all children for wildcard
      for (const child of node.children.values()) {
        if (this.dfs(child, word, i + 1)) return true;
      }
      return false;
    }
 
    if (!node.children.has(ch)) return false;
    return this.dfs(node.children.get(ch)!, word, i + 1);
  }
}

4.3 Rolling Hash — Rabin-Karp

function rabinKarp(text: string, pattern: string): number[] {
  const BASE = 31;
  const MOD = 1_000_000_007n;
  const n = text.length, m = pattern.length;
  const results: number[] = [];
 
  if (m > n) return results;
 
  // Precompute BASE^m % MOD
  let basePow = 1n;
  for (let i = 0; i < m; i++) basePow = (basePow * BigInt(BASE)) % MOD;
 
  const charCode = (c: string) => BigInt(c.charCodeAt(0) - 96);
 
  // Compute hash of pattern and first window
  let patHash = 0n, winHash = 0n;
  for (let i = 0; i < m; i++) {
    patHash = (patHash * BigInt(BASE) + charCode(pattern[i])) % MOD;
    winHash = (winHash * BigInt(BASE) + charCode(text[i])) % MOD;
  }
 
  for (let i = 0; i <= n - m; i++) {
    if (winHash === patHash) {
      // Hash collision possible — verify with actual comparison
      if (text.substring(i, i + m) === pattern) {
        results.push(i);
      }
    }
    // Roll the hash: remove text[i], add text[i+m]
    if (i < n - m) {
      winHash = (winHash * BigInt(BASE) - charCode(text[i]) * basePow + charCode(text[i + m]) + MOD) % MOD;
    }
  }
 
  return results;
}

4.4 Repeated DNA Sequences — Rolling Hash Application

// LeetCode #187
function findRepeatedDnaSequences(s: string): string[] {
  if (s.length <= 10) return [];
 
  const seen = new Map<number, number>(); // hash -> count
  const result = new Set<string>();
  const BASE = 4;
  const MOD = (1 << 30) - 1; // bit trick for fast mod
 
  const charMap: Record<string, number> = { A: 0, C: 1, G: 2, T: 3 };
  let hash = 0;
  const pow10 = Math.pow(BASE, 9); // BASE^(L-1)
 
  for (let i = 0; i < s.length; i++) {
    hash = (hash * BASE + charMap[s[i]]) & MOD;
 
    if (i >= 9) {
      const count = (seen.get(hash) ?? 0) + 1;
      seen.set(hash, count);
      if (count === 2) result.add(s.substring(i - 9, i + 1));
 
      // Roll out leftmost character
      hash = (hash - charMap[s[i - 9]] * pow10 * BASE) & MOD;
    }
  }
 
  return [...result];
}

4.5 Word Search II — Trie + DFS (Hard, Most Important)

// LeetCode #212 — Complete solution
class TrieNodeWS {
  children: (TrieNodeWS | null)[] = new Array(26).fill(null);
  word: string | null = null; // store complete word at end node
}
 
function findWords(board: string[][], words: string[]): string[] {
  // Build Trie from all words
  const root = new TrieNodeWS();
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) node.children[idx] = new TrieNodeWS();
      node = node.children[idx]!;
    }
    node.word = word;
  }
 
  const ROWS = board.length, COLS = board[0].length;
  const result: string[] = [];
 
  function dfs(r: number, c: number, node: TrieNodeWS): void {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;
    const ch = board[r][c];
    if (ch === '#') return; // already visited
 
    const idx = ch.charCodeAt(0) - 97;
    const nextNode = node.children[idx];
    if (!nextNode) return; // no words in Trie start with this path
 
    if (nextNode.word) {
      result.push(nextNode.word);
      nextNode.word = null; // de-duplicate: mark as found
    }
 
    board[r][c] = '#'; // mark visited
    dfs(r + 1, c, nextNode);
    dfs(r - 1, c, nextNode);
    dfs(r, c + 1, nextNode);
    dfs(r, c - 1, nextNode);
    board[r][c] = ch; // restore
  }
 
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      dfs(r, c, root);
    }
  }
 
  return result;
}

Tối ưu quan trọng cho Word Search II

Pruning: Sau khi tìm thấy word, set node.word = null để tránh duplicate. Nếu muốn mạnh hơn, xóa hẳn nút lá khỏi Trie sau khi tìm thấy. Điều này giúp tránh duyệt lại nhánh đã “cạn kiệt”.

4.6 Longest Common Prefix — Trie Approach

// O(S) where S = total characters in all strings
function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return "";
 
  const trie = new Trie();
  for (const s of strs) trie.insert(s);
 
  // Walk down Trie until: branching node, end-of-word, or empty
  let node = (trie as any).root as TrieNode;
  let prefix = "";
 
  while (true) {
    // Stop if this is end of a word (e.g., "app" is prefix of "apple")
    if (node.isEnd) break;
    // Stop if more than one child (branching)
    if (node.children.size !== 1) break;
 
    const [ch, child] = node.children.entries().next().value;
    prefix += ch;
    node = child;
  }
 
  return prefix;
}

5. Complexity Deep-dive

So sánh độ phức tạp chi tiết

Trie Operations:

Insert: $O (L)$ — L = độ dài word
Search: $O (L)$
StartsWith: $O (L)$
Space: $O (total_chars \times 26)$ — mỗi node có tối đa 26 children (ASCII)
Space với HashMap children: $O (total_chars)$ nhưng constant factor cao hơn

String Matching:

Algorithm	Preprocessing	Search	Total	Handles
Brute Force	$O (1)$	$O (NM)$	$O (NM)$	—
Rabin-Karp	$O (M)$	$O (N)$ avg	$O (N + M)$	Multiple patterns
KMP	$O (M)$	$O (N)$	$O (N + M)$	Single pattern
Trie+DFS	$O (\sum L_{i})$	$O (N \times 4^{L})$	Board problems	Multi-pattern in 2D

Rabin-Karp worst case

Worst case $O (NM)$ xảy ra khi tất cả hash đều collision. Ví dụ: text = “aaaaaa”, pattern = “aaa”. Chọn hash function tốt và verify khi match để tránh.

Word Search II — Tại sao Trie beats brute force?

Brute force: Với W words, mỗi word DFS $O (4^{L})$ → tổng $O (W \times N \times 4^{L})$
Trie: Chia sẻ prefix search, pruning sớm khi không còn word nào match → thực tế nhanh hơn rất nhiều

6. Edge Cases & Pitfalls

Những lỗi phổ biến trong interview

Trie:

// BUG: Quên check isEnd — chỉ check node tồn tại
search("app"): node tồn tại (là prefix của "apple") nhưng isEnd = false!
// FIX: Luôn return node.isEnd tại cuối search()
 
// BUG: Dùng array[26] nhưng input có uppercase + lowercase mixed
// FIX: Chuẩn hóa về lowercase trước, hoặc dùng Map<string, TrieNode>

Rolling Hash:

// BUG: Hash collision — hai string khác nhau có cùng hash
// FIX: Khi hash match, LUÔN verify bằng string comparison thực tế
 
// BUG: Overflow với số lớn
// FIX: Dùng BigInt hoặc modular arithmetic với prime lớn (1e9+7)
 
// BUG: Rolling hash khi remove char đầu bị âm
// FIX: (hash - val + MOD) % MOD — luôn thêm MOD trước khi mod

Trie Memory:

// Trie với array[26] children:
// 1 node = 26 pointers × 8 bytes = 208 bytes
// 1 million chars = 200MB+ memory!
// FIX: Dùng Map<string, TrieNode> nếu sparse characters
// hoặc chỉ dùng array[26] khi biết chắc chỉ có lowercase letters

Unicode vs ASCII

Nếu input có Unicode (tiếng Việt, emoji…), charCodeAt(0) - 97 sẽ cho index âm hoặc index > 25. Luôn hỏi interviewer: “Input chỉ có lowercase English letters không?” Nếu không chắc, dùng HashMap.

Word Search II — Pitfall quan trọng:

// BUG: Không restore board[r][c] sau DFS
board[r][c] = '#'; // mark visited
dfs(...)
board[r][c] = ch;  // MUST restore! Không có dòng này → bug
 
// BUG: Không de-duplicate khi một word được tìm thấy nhiều lần
// FIX: nextNode.word = null sau khi push vào result

7. Pattern Recognition

Nhận diện bài toán Trie/String Matching

Keywords → Trie:

“autocomplete”, “suggest words with prefix”
“starts with prefix”, “count words starting with”
“word search in board với nhiều words” (multi-pattern)
“implement dictionary”, “add word / search word”
“longest word in dictionary that is a subsequence”
“maximum XOR” (Binary Trie!)

Keywords → Rolling Hash:

“repeated substrings of length K”
“find pattern in text” (single occurrence)
“longest duplicate substring” (binary search + rolling hash)
“detect plagiarism” (substring matching)

Keywords → KMP:

“shortest period of string”
“string matching guaranteed O(N+M)”
“find all occurrences of pattern”

Binary Trie — Bonus

Trie không chỉ dùng cho characters! Binary Trie (mỗi node có 2 children: 0 và 1) dùng để tối ưu Maximum XOR problems. Ví dụ: #421 Maximum XOR of Two Numbers in an Array.

8. Top LeetCode Problems

#	Tên bài	Độ khó	Key technique
#208	Implement Trie (Prefix Tree)	Medium	Core Trie
#211	Design Add and Search Words	Medium	Trie + DFS wildcard
#212	Word Search II	Hard	Trie + DFS on board
#1392	Longest Happy Prefix	Hard	KMP failure function
#187	Repeated DNA Sequences	Medium	Rolling Hash
#14	Longest Common Prefix	Easy	Trie (or simple)
#336	Palindrome Pairs	Hard	Trie + palindrome check
#421	Maximum XOR	Medium	Binary Trie

Complete Solution: #212 Word Search II (Hard)

Đây là bài được hỏi nhiều nhất ở Google/Meta về Trie. Giải pháp dưới đây có đầy đủ optimization.

// LeetCode #212 — Word Search II
// Time: O(M × N × 4^L) where L = max word length
// Space: O(total chars in words) for Trie
 
class TrieNode212 {
  children: (TrieNode212 | null)[] = new Array(26).fill(null);
  word: string | null = null;
  count: number = 0; // track how many words pass through this node
}
 
function findWords212(board: string[][], words: string[]): string[] {
  const root = new TrieNode212();
 
  // Insert all words into Trie
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) node.children[idx] = new TrieNode212();
      node = node.children[idx]!;
      node.count++;
    }
    node.word = word;
  }
 
  const ROWS = board.length;
  const COLS = board[0].length;
  const result: string[] = [];
 
  function dfs(r: number, c: number, node: TrieNode212): void {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;
    const ch = board[r][c];
    if (ch === '#') return;
 
    const idx = ch.charCodeAt(0) - 97;
    const next = node.children[idx];
    if (!next || next.count === 0) return; // pruning: no words left in subtree
 
    if (next.word) {
      result.push(next.word);
      next.word = null; // avoid duplicates
    }
 
    board[r][c] = '#';
    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);
    board[r][c] = ch;
 
    // Pruning optimization: if all words in this subtree found, decrement count
    if (next.word === null && next.children.every(child => !child || child.count === 0)) {
      next.count = 0;
    }
  }
 
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      dfs(r, c, root);
    }
  }
 
  return result;
}
 
// Test
console.log(findWords212(
  [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
  ["oath","pea","eat","rain"]
)); // ["eat","oath"]

9. Self-Assessment Checklist

Kiểm tra bản thân trước khi interview

Quick revision

Nếu chỉ có 20 phút ôn, tập trung vào: Trie insert/search/startsWith, Word Search II pattern (Trie + DFS + restore board), và Rolling Hash collision handling.

lthieu's notes

Explorer

06-String-Matching-Trie

Buổi 06 — String Matching & Trie

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Trie cho [“apple”, “app”, “apply”, “apt”]

3.2 Rolling Hash — Sliding Window

3.3 KMP Failure Function

4. TypeScript Template

4.1 TrieNode & Trie — Core Implementation

4.2 Trie với Wildcard Search (’.‘)

4.3 Rolling Hash — Rabin-Karp

4.4 Repeated DNA Sequences — Rolling Hash Application

4.5 Word Search II — Trie + DFS (Hard, Most Important)

4.6 Longest Common Prefix — Trie Approach

5. Complexity Deep-dive

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

Complete Solution: #212 Word Search II (Hard)

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks