Word Search: DFS backtracking đánh dấu và xoá dấu trên chính đường đi của mình

Word Search là bài toán khiến backtracking trở nên cụ thể với tôi. Trước đó, backtracking mãi là một ý tưởng mơ hồ — thử một cái gì đó, hoàn tác nó, thử cái tiếp theo. Ở đây grid cho nó một trực giác vật lý: bạn đang thực sự đi bộ theo một con đường xuyên qua các ô, để lại vết # phía sau, và xoá chúng khi quay lui. Nếu điều đó nghe có vẻ hiển nhiên trong lý thuyết, thì thực tế không phải vậy khi tôi lần đầu nhìn vào board 3x4 và phải trả lời câu hỏi: "làm sao tránh ghé thăm lại một ô mà tôi đang đứng trên nó?"

LeetCode 79 yêu cầu: cho một board ký tự m x n và một chuỗi word, trả về true nếu word có thể được đánh vần bằng cách di chuyển ngang hoặc dọc qua các ô liền kề, mỗi ô chỉ dùng một lần.

Constraints nói gì với bạn

1 <= m, n <= 6. Board rất nhỏ. Tối đa 36 ô. 1 <= word.length <= 15. Từ cần tìm hoàn toàn vừa trong một board 6x6 hai lần và còn dư.

Worst-case complexity của DFS backtracking trên bài này là O(m _ n _ 4^L), trong đó L là độ dài từ. Thế vào các giá trị tối đa thực tế: 6 _ 6 _ 4^15 = 36 * 1,073,741,824. Tức là khoảng 38 tỷ về mặt lý thuyết. Thực tế backtracking pruning rất mạnh — ngay khi bất kỳ ký tự nào không khớp, bạn cắt toàn bộ subtree đó — nên performance thực tế không đến gần giới hạn trên này. Nhưng con số đó nói lên điều quan trọng: các giá trị constraint được chọn để backtracking khả thi, không phải thoải mái. Người ra đề thực chất đang nói "approach đúng là backtracking, và grid đủ nhỏ để ngay cả version naive cũng không bị timeout."

Nếu m và n là 100, backtracking đã chết và bạn cần thứ gì đó khác về bản chất. Ở 6x6, giới hạn trên vừa đủ chấp nhận được, và bất kỳ tối ưu early-exit nào cũng cho bạn thở phào đáng kể.

Một điều nữa constraints nói: không có ký tự đặc biệt, chỉ có chữ cái tiếng Anh hoa và thường. Điều đó có nghĩa bạn có thể dùng # làm sentinel cho "ô này đang được sử dụng" mà không bao giờ va chạm với nội dung board. Đây chính là điều khiến in-place marking hoạt động.

Approach cơ bản: DFS backtracking

Cấu trúc ở đây là pattern choose-explore-unchoose kinh điển trong series này. Với mỗi ô bắt đầu, bạn commit vào nó (đánh dấu), đệ quy vào 4 ô láng giềng, rồi uncommit (khôi phục). Recursion mang thêm một tham số: đã match được bao nhiêu ký tự trong word.

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
 
        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True
            if row < 0 or row >= rows or col < 0 or col >= cols:
                return False
            if board[row][col] != word[index]:
                return False
 
            # Đánh dấu ô này đang được dùng trên path hiện tại
            temp = board[row][col]
            board[row][col] = '#'
 
            found = (
                dfs(row - 1, col, index + 1) or
                dfs(row + 1, col, index + 1) or
                dfs(row, col - 1, index + 1) or
                dfs(row, col + 1, index + 1)
            )
 
            # Khôi phục — quan trọng cho tính đúng đắn khi thử ô bắt đầu khác
            board[row][col] = temp
            return found
 
        for i in range(rows):
            for j in range(cols):
                if dfs(i, j, 0):
                    return True
        return False

public class Solution {
    public bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (DFS(board, word, i, j, 0, rows, cols))
                    return true;
 
        return false;
    }
 
    private bool DFS(char[][] board, string word, int row, int col, int index, int rows, int cols) {
        if (index == word.Length) return true;
        if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
        if (board[row][col] != word[index]) return false;
 
        char temp = board[row][col];
        board[row][col] = '#';
 
        bool found = DFS(board, word, row - 1, col, index + 1, rows, cols)
                  || DFS(board, word, row + 1, col, index + 1, rows, cols)
                  || DFS(board, word, row, col - 1, index + 1, rows, cols)
                  || DFS(board, word, row, col + 1, index + 1, rows, cols);
 
        board[row][col] = temp;
        return found;
    }
}

or short-circuit trong Python làm điều gì đó hữu ích: ngay khi một hướng trả về true, ba hướng còn lại bị bỏ qua. Trong C# operator || làm điều tương tự. Đây là pruning ngầm định — subtree của path đã tìm thấy thoát ra ngay lập tức, nhưng bước restore vẫn chạy (board[row][col] = temp) để board sạch cho ô bắt đầu tiếp theo.

Trace từng bước qua "ABCCED"

Board:

A B C E
S F C S
A D E E

Word: ABCCED

Trace dưới đây dùng toạ độ (row, col), zero-indexed.

Bắt đầu từ (0,0): board[0][0]='A', word[0]='A' -> match
  Đánh dấu (0,0)='#', thử các láng giềng, index=1
  Thử (row-1,col): (-1,0) -> out of bounds, return false
  Thử (row+1,col): (1,0) -> board[1][0]='S', word[1]='B' -> không khớp, return false
  Thử (row,col-1): (0,-1) -> out of bounds, return false
  Thử (row,col+1): (0,1) -> board[0][1]='B', word[1]='B' -> match
    Đánh dấu (0,1)='#', thử các láng giềng, index=2
    Thử (row+1,col): (1,1) -> board[1][1]='F', word[2]='C' -> không khớp
    Thử (row,col+1): (0,2) -> board[0][2]='C', word[2]='C' -> match
      Đánh dấu (0,2)='#', thử các láng giềng, index=3
      Thử (row+1,col): (1,2) -> board[1][2]='C', word[3]='C' -> match
        Đánh dấu (1,2)='#', thử các láng giềng, index=4
        Thử (row+1,col): (2,2) -> board[2][2]='E', word[4]='E' -> match
          Đánh dấu (2,2)='#', thử các láng giềng, index=5
          Thử (row,col+1): (2,3) -> board[2][3]='E', word[5]='D' -> không khớp
          Thử (row,col-1): (2,1) -> board[2][1]='D', word[5]='D' -> match
            Đánh dấu (2,1)='#', index=6
            index == len(word) -> return True

Decision tree của DFS:

Mỗi khi một nhánh gặp ký tự không khớp hoặc ô #, subtree đó sụp đổ ngay lập tức. Phép restore ở mỗi tầng (board[row][col] = temp) là thứ cho phép các ô bắt đầu khác thấy một board sạch.

Approach tối ưu với frequency pruning

Version cơ bản có một vấn đề có thể tránh được: nó thử mọi ô làm điểm bắt đầu, kể cả những ô không thể bắt đầu từ đó. Version tối ưu thêm hai bước pruning trước vòng lặp DFS.

Đầu tiên, đếm số lần mỗi ký tự xuất hiện trên board. Nếu word cần nhiều hơn số lần xuất hiện của bất kỳ ký tự nào, trả về false ngay — không cần DFS.

Thứ hai, so sánh tần suất của ký tự đầu tiên trong word với tần suất của ký tự cuối cùng. Nếu ký tự cuối hiếm hơn ký tự đầu, đảo ngược word và tìm kiếm ngược lại. Điều này đúng vì một đường đi hợp lệ theo cả hai chiều — nếu "ABCCED" tồn tại, thì "DECBCA" cũng tồn tại dọc theo cùng đường đi đó. Bắt đầu từ điểm kết thúc hiếm hơn có nghĩa là ít ô bắt đầu hợp lệ hơn, ít DFS root hơn, ít node được duyệt hơn.

from collections import Counter
 
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
 
        # Đếm tần suất ký tự trên board
        board_count: Counter[str] = Counter()
        for row in board:
            board_count.update(row)
 
        # Pruning: word yêu cầu ký tự không có đủ số lượng
        word_count = Counter(word)
        for ch, cnt in word_count.items():
            if board_count[ch] < cnt:
                return False
 
        # Heuristic hướng: bắt đầu từ đầu hiếm hơn
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]
 
        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True
            if row < 0 or row >= rows or col < 0 or col >= cols:
                return False
            if board[row][col] != word[index]:
                return False
 
            temp = board[row][col]
            board[row][col] = '#'
 
            found = (
                dfs(row - 1, col, index + 1) or
                dfs(row + 1, col, index + 1) or
                dfs(row, col - 1, index + 1) or
                dfs(row, col + 1, index + 1)
            )
 
            board[row][col] = temp
            return found
 
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

public class Solution {
    public bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
 
        // Đếm tần suất ký tự trên board
        var boardCount = new Dictionary<char, int>();
        foreach (var row in board)
            foreach (char c in row)
                boardCount[c] = boardCount.GetValueOrDefault(c, 0) + 1;
 
        // Pruning: thoát sớm nếu ký tự trong word không đủ
        var wordCount = new Dictionary<char, int>();
        foreach (char c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
            if (!boardCount.ContainsKey(c) || wordCount[c] > boardCount[c])
                return false;
        }
 
        // Heuristic hướng: đảo ngược word để bắt đầu từ ký tự hiếm hơn
        if (boardCount[word[0]] > boardCount[word[word.Length - 1]]) {
            char[] arr = word.ToCharArray();
            Array.Reverse(arr);
            word = new string(arr);
        }
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (board[i][j] == word[0] && DFS(board, word, i, j, 0, rows, cols))
                    return true;
 
        return false;
    }
 
    private bool DFS(char[][] board, string word, int row, int col, int index, int rows, int cols) {
        if (index == word.Length) return true;
        if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
        if (board[row][col] != word[index]) return false;
 
        char temp = board[row][col];
        board[row][col] = '#';
 
        bool found = DFS(board, word, row - 1, col, index + 1, rows, cols)
                  || DFS(board, word, row + 1, col, index + 1, rows, cols)
                  || DFS(board, word, row, col - 1, index + 1, rows, cols)
                  || DFS(board, word, row, col + 1, index + 1, rows, cols);
 
        board[row][col] = temp;
        return found;
    }
}

Frequency check tốn O(m * n + L) thời gian và O(1) không gian nếu dùng mảng fixed-size cho 52 ký tự có thể có. Nó tự hoàn vốn ngay lập tức trên bất kỳ board nào mà word chứa ký tự chỉ xuất hiện một lần nhưng word cần nó hai lần.

Heuristic đảo ngược khó nội tâm hoá hơn. Hãy tưởng tượng board có 20 ô 'A' và 1 ô 'Z', và word là "AZ...". Bắt đầu từ tất cả 20 ô 'A', hầu hết đường DFS sẽ nhanh chóng gặp ngõ cụt, nhưng bạn vẫn khởi tạo 20 recursion tree. Đảo ngược thành "...ZA" và bạn chỉ bắt đầu từ đúng 1 ô. DFS body hoàn toàn giống nhau — bạn chỉ cho mình 19 lần gọi root ít hơn.

Các edge case thực sự quan trọng

Ô đơn, word một ký tự. board = [["A"]], word = "A". DFS vào tại (0,0), index=0 khớp, đánh dấu ô, đệ quy, ngay lập tức đạt index == 1 == len(word) và trả về true. Sau đó restore chạy. Điều này đúng, và đáng kiểm tra tường minh vì base case index == len(word) phải kích hoạt trước bất kỳ bounds check nào.

Word dài hơn số ô board có. Nếu word.length > m * n, không có path nào qua board có thể đánh vần được nó — mỗi ô chỉ được dùng một lần. Version tối ưu bắt lấy điều này ngầm thông qua frequency check (ít nhất một ký tự sẽ cần nhiều hơn số lần xuất hiện của nó). Version cơ bản không bắt sớm, nhưng DFS vẫn trả về false đúng vì path không thể quay lại ô đã thăm.

Tất cả ô giống nhau, word lặp ký tự đó. board = [["A","A"],["A","A"]], word = "AAAA". DFS có thể snake qua board mà không ghé lại ô nào vì marker # chặn backtrack về các ô đã được claim. Một board 2x2 với 4 ô 'A' đánh vần "AAAA" đúng một lần (chỉ có một Hamiltonian path qua board 2x2, tính theo rotation). In-place marker xử lý điều này đúng mà không cần logic thêm.

Word hoàn toàn không có trong board. DFS duyệt hết tất cả ô bắt đầu và tất cả path từ mỗi ô. false được trả về sau khi tất cả đều thất bại. Đây là worst case về performance — không có early termination từ việc tìm thấy word.

Ký tự cuối và đầu word giống nhau và hiếm. Đây là lúc heuristic đảo ngược có thể gây hại nếu implement không cẩn thận: word[0] == word[-1] nghĩa là đảo ngược word tạo ra ký tự bắt đầu khác khi kiểm tra, nhưng boardCount[word[0]] == boardCount[word[-1]] nên điều kiện boardCount[word[0]] > boardCount[word[-1]] là false và không có đảo ngược nào xảy ra. An toàn.

Độ phức tạp và thực tế nên dùng cái nào

Cả hai có cùng giới hạn thời gian asymptotic. Sự khác biệt về không gian là K — số ký tự riêng biệt trên board, tối đa là 52 trong worst case nhưng thực tế nhỏ. L là độ dài word, chiếm ưu thế trong độ sâu call stack.

Giới hạn big-O trông đáng sợ cho đến khi bạn nhớ rằng hệ số 4^L giả định mỗi ô luôn có 4 láng giềng khả thi. Điều này chỉ đúng với ô sâu trong nội thất của board rất lớn. Trên grid 6x6, ô góc có 2 láng giềng, ô cạnh có 3. Ở độ sâu k vào word, tập ứng viên thu hẹp khi path quay trở lại và gặp marker #. Số node thực sự được duyệt ít hơn rất nhiều so với worst case lý thuyết.

Tôi sẽ dùng version tối ưu cho bất kỳ context production nào, nhưng chủ yếu không phải vì frequency pruning — mà vì heuristic đảo ngược. Frequency check là một preflight O(m*n) tốt mà gần như không tốn gì, nhưng heuristic đảo ngược là cái quan trọng khi ký tự cuối của word hiếm hơn ký tự đầu nhiều, điều này xảy ra trong dataset thực thường xuyên hơn các ví dụ sạch gợi ý. Trên board 6x6 nó có thể tiết kiệm 30% DFS call trong các trường hợp pathological.

Version cơ bản là cái đúng để viết trước, hiểu hoàn toàn, và giải thích trong interview. Sau khi nó đúng, việc thêm hai tối ưu hóa chỉ là cơ học.

Đánh dấu in-place so với ma trận visited riêng

Approach thay thế dùng ma trận bool[m][n] visited riêng thay vì mutate board. Cả hai đều đúng. Trade-off:

In-place marking dùng O(L) space (chỉ call stack), dùng sentinel # như một phần của value domain, và mutate input. Điểm cuối đó có thể là vấn đề nếu caller kỳ vọng board không thay đổi sau khi gọi hàm. Trong context interview khi function signature truyền board và bạn dự kiến để nó nguyên vẹn, bạn sẽ muốn dùng approach visited matrix.

Visited matrix dùng O(m * n + L) space — một boolean grid đầy đủ cộng với call stack. Nó không mutate input, sạch hơn nếu bạn đang viết library. Code gần như giống hệt; chỉ thay board[row][col] = '#' bằng visited[row][col] = true và kiểm tra bounds tương ứng.

Với LeetCode submission, in-place marking là lựa chọn thông thường và khôi phục board đúng cách, nên function có vẻ để board nguyên vẹn khi trả về. Tôi gọi đây là chấp nhận được cho competitive programming nhưng đáng ghi chú trong production code.

Vị trí trong series và những gì tiếp theo

Đây là bài thứ tư trong series backtracking, và đây là lần đầu tiên variant "grid" của backtracking xuất hiện. Các bài trước (Subsets, Combinations, Permutations) đều làm việc trên một flat list với một index đơn giản theo dõi phần tử nào còn khả dụng. Ở đây state là không gian — bạn theo dõi ô nào đang trên path hiện tại, không phải array index nào bạn đã qua.

Decision tree ở đây rẽ nhánh theo hướng thay vì chọn phần tử. Mỗi node trong tree là một triple (row, col, index). Branching factor tối đa là 4. Độ sâu là word.length. Framing đó — decision tree với branching có giới hạn và độ sâu hữu hạn — áp dụng cho cả bài toán list 1D lẫn grid 2D; grid chỉ làm nó trực quan hơn mà thôi.

Bốn bài toán xây dựng trên cùng hình dạng này:

LeetCode 212 — Word Search II. Cùng grid, nhưng tìm tất cả các từ từ một dictionary cho trước đồng thời. Naive: chạy LeetCode 79 một lần cho mỗi từ. Tốt hơn: xây dựng một Trie của tất cả các từ, DFS grid một lần, kiểm tra mỗi ô với Trie prefix. Twist là DFS giờ phải báo cáo tất cả path, không dừng ở match đầu tiên, và Trie là cơ chế pruning thay vì frequency check ký tự.

LeetCode 200 — Number of Islands. DFS trên grid nữa, nhưng mục tiêu là đếm connected component, không match chuỗi. Không cần backtracking — bạn đánh dấu ô là visited vĩnh viễn vì không bao giờ cần tái sử dụng chúng. Hiểu Word Search khiến Number of Islands gần như trivial, vì bạn không cần hoàn tác bất cứ thứ gì.

LeetCode 130 — Surrounded Regions. DFS để xác định các region chạm vào border, sau đó lật mọi thứ không chạm. Cùng cơ chế duyệt grid, nhưng mục tiêu tìm kiếm là topological (kết nối với border) thay vì sequential (khớp ký tự).

LeetCode 329 — Longest Increasing Path in a Matrix. DFS trên grid trong đó constraint là mỗi bước phải lớn hơn bước trước. Không cần đánh dấu visited vì constraint strictly-increasing ngăn việc ghé lại. Memoization biến bài này từ exponential thành O(m * n). Đây là bài tự nhiên tiếp theo sau Word Search nếu bạn muốn xem điều gì xảy ra khi bạn bỏ constraint "không được ghé lại" và thay bằng một value constraint.