Snowflake 面試題：字元矩陣中查找單詞

題目描述

Given an m by n matrix of characters and a list of strings, 
return the strings that are found in the m by n matrix.

範例：

Matrix:

[
  ['a', 'b', 'c'],
  ['d', 'e', 'f']
]

Words:

['abe', 'xyz', 'abf']

Output:

['abe']

問題分析

這道題讓你從一個**字元矩陣（m×n）中，判斷給定的單詞列表中哪些可以在矩陣裡找到。單詞通常需要通過相鄰字元（橫向或縱向）**連續組成。

這與 LeetCode 上的 Word Search / Word Search II 非常類似，是一個典型的 DFS + 回溯的考點。

核心點包括：

• 從矩陣中尋找單詞的首字母
• 使用 DFS 或 BFS 去檢查整個單詞是否能匹配
• 訪問過的格子不能重複使用
• 需要在搜尋過程中進行剪枝，否則會超時

解法二：Trie + DFS（優化版）

對於多個單詞的搜尋，使用 Trie（前綴樹） 可以大幅優化：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def find_words(self, matrix, words):
        """
        使用 Trie 優化多單詞搜尋
        """
        if not matrix or not matrix[0]:
            return []
        
        # 1. 構建 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
        
        m, n = len(matrix), len(matrix[0])
        result = []
        
        def dfs(i, j, node):
            """DFS 搜尋"""
            if node.word:
                result.append(node.word)
                node.word = None  # 避免重複添加
            
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            
            char = matrix[i][j]
            if char not in node.children:
                return
            
            # 標記訪問
            matrix[i][j] = '#'
            
            # 四個方向搜尋
            for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
                dfs(i + di, j + dj, node.children[char])
            
            # 恢復現場
            matrix[i][j] = char
            
            # 剪枝：如果子節點為空，刪除當前節點
            if not node.children[char].children:
                del node.children[char]
        
        # 2. 從每個位置開始 DFS
        for i in range(m):
            for j in range(n):
                if matrix[i][j] in root.children:
                    dfs(i, j, root)
        
        return result

時間複雜度： O(m × n × 4^L)，比解法一快很多

總結

Snowflake 字元矩陣搜尋題考察點：

1. DFS/BFS 基礎：矩陣遍歷和路徑搜尋
2. 回溯技巧：visited 集合的使用和恢復
3. Trie 優化：多單詞搜尋的性能優化
4. 剪枝策略：避免不必要的搜尋

oavoservice 專注於 Snowflake / Google / Amazon 等大廠面試輔導，提供 OA 代做、VO 即時輔助等服務。如需幫助，歡迎聯繫我們。

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。