# 字符矩阵中查找单词——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.
Example:
Matrix:
[
['a', 'b', 'c'],
['d', 'e', 'f']
]
Words:
['abe', 'xyz', 'abf']
Output:
['abe']
问题分析
这道题让你从一个**字符矩阵（m×n）中，判断给定的单词列表中哪些可以在矩阵里找到。单词通常需要通过相邻字符（横向或纵向）**连续组成。
这与 LeetCode 上的 Word Search / Word Search II 非常类似，是一个典型的 DFS + 回溯的考点。
核心点包括：
- 从矩阵中寻找单词的首字母
- 使用 DFS 或 BFS 去检查整个单词是否能匹配
- 访问过的格子不能重复使用
- 需要在搜索过程中进行剪枝，否则会超时
属于考察矩阵搜索、回溯、剪枝策略的典型面试高频题。
解法一：DFS + 回溯（单词逐个搜索）
def find_words(matrix, words):
"""
在矩阵中查找单词列表
"""
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
result = []
def dfs(i, j, word, index, visited):
"""DFS 搜索单词"""
if index == len(word):
return True
if (i < 0 or i >= m or j < 0 or j >= n or
(i, j) in visited or matrix[i][j] != word[index]):
return False
visited.add((i, j))
# 四个方向搜索
found = (dfs(i+1, j, word, index+1, visited) or
dfs(i-1, j, word, index+1, visited) or
dfs(i, j+1, word, index+1, visited) or
dfs(i, j-1, word, index+1, visited))
visited.remove((i, j)) # 回溯
return found
for word in words:
found = False
for i in range(m):
for j in range(n):
if matrix[i][j] == word[0]:
if dfs(i, j, word, 0, set()):
result.append(word)
found = True
break
if found:
break
return result
时间复杂度： O(k × m × n × 4^L)，其中 k 是单词数量，L 是单词平均长度
解法二：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)，比解法一快很多
解法三：双向 BFS（适用于长单词）
from collections import deque
def find_words_bfs(matrix, words):
"""
使用 BFS 搜索单词
"""
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
result = []
def bfs(word):
"""BFS 搜索单个单词"""
queue = deque()
# 找到所有首字母位置
for i in range(m):
for j in range(n):
if matrix[i][j] == word[0]:
queue.append((i, j, 0, {(i, j)}))
while queue:
i, j, idx, visited = queue.popleft()
if idx == len(word) - 1:
return True
for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
ni, nj = i + di, j + dj
if (0 <= ni < m and 0 <= nj < n and
(ni, nj) not in visited and
matrix[ni][nj] == word[idx + 1]):
new_visited = visited.copy()
new_visited.add((ni, nj))
queue.append((ni, nj, idx + 1, new_visited))
return False
for word in words:
if bfs(word):
result.append(word)
return result
常见变种
1. 允许对角线移动
# 八个方向
directions = [(0,1), (0,-1), (1,0), (-1,0),
(1,1), (1,-1), (-1,1), (-1,-1)]
2. 单词可以重复使用格子
# 不需要 visited 集合，直接搜索
def dfs(i, j, word, index):
if index == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] != word[index]:
return False
return any(dfs(i+di, j+dj, word, index+1)
for di, dj in directions)
3. 找出所有可能的路径
def find_all_paths(matrix, word):
"""返回所有匹配路径"""
paths = []
def dfs(i, j, index, path):
if index == len(word):
paths.append(path[:])
return
if (i < 0 or i >= m or j < 0 or j >= n or
(i, j) in path or matrix[i][j] != word[index]):
return
path.add((i, j))
for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
dfs(i + di, j + dj, index + 1, path)
path.remove((i, j))
for i in range(m):
for j in range(n):
if matrix[i][j] == word[0]:
dfs(i, j, 0, set())
return paths
优化技巧
- 提前剪枝：如果单词长度 > m×n，直接跳过
- 字符频率检查：统计矩阵字符频率，如果单词包含不存在的字符，跳过
- Trie 剪枝：搜索过程中删除已匹配的分支
- 缓存结果：记录已搜索过的起点和单词组合
总结
Snowflake 字符矩阵搜索题考察点：
- DFS/BFS 基础：矩阵遍历和路径搜索
- 回溯技巧：visited 集合的使用和恢复
- Trie 优化：多单词搜索的性能优化
- 剪枝策略：避免不必要的搜索
oavoservice 专注于 Snowflake / Google / Amazon 等大厂面试辅导，提供 OA 代做、VO 实时辅助等服务。如需帮助，欢迎联系我们。
需要面试真题？ 立刻联系微信 Coding0201，获得真题。