單詞搜尋#

LeetCode 212: Word Search II#

題目#

給定二維字元矩陣和單詞列表，找出所有存在於矩陣中的單詞。

單詞由相鄰字元組成（上下左右四連通）
同一位置的字母不能重複使用

Board:
o a a n
e t a e
i h k r
a i f l

Words: ["oath", "pea", "eat", "rain"]
Output: ["oath", "eat"]

解法演進#

方法一：暴力 DFS（會超時）#

對每個單詞，在矩陣中執行 DFS 搜尋。

問題：單詞多時，重複掃描矩陣。

方法二：Trie + DFS（最佳）#

將所有單詞建成 Trie
走訪矩陣每個位置作為起點
DFS 同時在矩陣和 Trie 中行走
Trie 中無路可走時剪枝

核心優化：一次 DFS 同時檢查所有以當前路徑為前綴的單詞。

Trie + DFS 實現#

完整程式碼

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # 儲存完整單詞

class Solution:
    def findWords(self, board, words):
        # 建立 Trie
        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  # 標記單詞結尾

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

        def dfs(r, c, node):
            char = board[r][c]

            # 剪枝：Trie 中無此字元
            if char not in node.children:
                return

            next_node = node.children[char]

            # 找到完整單詞
            if next_node.word:
                result.append(next_node.word)
                next_node.word = None  # 避免重複

            # 標記已訪問
            board[r][c] = '#'

            # 四個方向擴展
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    dfs(nr, nc, next_node)

            # 回溯
            board[r][c] = char

        # 從每個位置開始搜尋
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

關鍵技巧#

1. 傳遞 Trie 節點（而非字串）#

# 低效：每次從根節點搜尋
def dfs(r, c, current_str):
    if not trie.startsWith(current_str):  # O(len)
        return

# 高效：直接傳遞當前節點
def dfs(r, c, node):
    if char not in node.children:  # O(1)
        return

傳遞節點使「是否有此前綴」的判斷從 O(len) 降為 O(1)。

2. 原地標記 vs visited 陣列#

方法	優點	缺點
修改 board	省空間	破壞原資料
visited 陣列	不破壞資料	多用 O(mn) 空間

# 原地標記
board[r][c] = '#'  # 標記
# ... DFS ...
board[r][c] = char  # 回溯時恢復

3. 方向陣列#

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        dfs(nr, nc, node)

複雜度分析#

項目	複雜度
建立 Trie	O(W × L)，W 為單詞數，L 為平均長度
DFS 搜尋	O(M × N × 4^L)，最壞情況
空間	O(W × L) Trie + O(L) 遞迴堆疊

實際執行時，Trie 的剪枝會大幅減少搜尋次數。

常見錯誤#

回溯遺漏：DFS 返回前必須恢復狀態（board 或 visited）。

# 錯誤：忘記回溯
def dfs(r, c, node):
    board[r][c] = '#'
    for ...:
        dfs(...)
    # 缺少：board[r][c] = char

# 正確
def dfs(r, c, node):
    temp = board[r][c]
    board[r][c] = '#'
    for ...:
        dfs(...)
    board[r][c] = temp  # 回溯