← 返回博客列表
VO Bloomberg

Bloomberg 面试题：网格单词搜索（Word Search）

2025-12-11

题目描述

给定一个二维字符矩阵和一个目标单词，判断单词是否能在矩阵中找到。单词必须由相邻格子（水平或垂直）的字符按顺序组成，每个格子只能使用一次。

示例

矩阵:
board = [
  ['B', 'C', 'F', 'E'],
  ['E', 'A', 'B', 'L'],
  ['B', 'C', 'D', 'O'],
  ['E', 'B', 'M', 'O'],
  ['R', 'G', 'D', 'E'],
]

word = "BLOOMBERG" -> true  (可以在矩阵中找到路径)
word = "BOB"       -> false (无法找到有效路径)
word = "BEABLE"    -> true  (可以找到)

解题思路

典型的 DFS + 回溯 问题：

  1. 遍历矩阵，找到与单词首字母相同的位置作为起点
  2. 从起点开始 DFS，向四个方向扩展
  3. 使用 visited 数组标记已访问的格子
  4. 如果找到完整路径返回 true

Python 实现

def exist(board: list, word: str) -> bool:
    if not board or not board[0] or not word:
        return False
    
    rows, cols = len(board), len(board[0])
    
    def dfs(r: int, c: int, index: int) -> bool:
        # 找到完整单词
        if index == len(word):
            return True
        
        # 边界检查
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        
        # 字符不匹配或已访问
        if board[r][c] != word[index]:
            return False
        
        # 标记已访问
        temp = board[r][c]
        board[r][c] = '#'
        
        # 向四个方向搜索
        found = (dfs(r + 1, c, index + 1) or
                 dfs(r - 1, c, index + 1) or
                 dfs(r, c + 1, index + 1) or
                 dfs(r, c - 1, index + 1))
        
        # 回溯：恢复原值
        board[r][c] = 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

优化版本（预检查）

from collections import Counter

def exist_optimized(board: list, word: str) -> bool:
    # 预检查：矩阵中的字符是否足够
    board_counter = Counter()
    for row in board:
        board_counter.update(row)
    
    word_counter = Counter(word)
    for char, count in word_counter.items():
        if board_counter[char] < count:
            return False
    
    # 优化：如果末尾字符更少，反转搜索
    if board_counter[word[0]] > board_counter[word[-1]]:
        word = word[::-1]
    
    # 执行 DFS
    return exist(board, word)

复杂度分析

进阶：搜索多个单词

如果需要在矩阵中搜索多个单词，可以使用 Trie 树 优化：

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

def find_words(board: list, words: list) -> list:
    # 构建 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: int, c: int, node: TrieNode):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        
        char = board[r][c]
        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 [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dfs(r + dr, c + dc, next_node)
        board[r][c] = char
    
    for i in range(rows):
        for j in range(cols):
            dfs(i, j, root)
    
    return result

需要面试辅助服务？联系我们

需要面试真题？ 立刻联系微信 Coding0201，获得真题。