作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入格式
- board：一个二维字符数组。
- word：一个字符串，代表需要搜索的单词。
输出格式
- 返回一个布尔值，表示单词是否在网格中。
示例
示例 1
输入: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ], word = "ABCCED" 输出: true
示例 2
输入: board = [ ['a','b'], ['c','d'] ], word = "abcd" 输出: false
方法一：回溯法
解题步骤
- 遍历网格：从每一个可能的起点开始，尝试所有路径直到找到匹配的单词。
- 递归搜索：从一个字符开始，递归地搜索四个方向（上、下、左、右）是否可以形成单词。
- 边界和条件：确保搜索不越界，且当前字符与单词字符匹配，未被访问过。
完整的规范代码
def exist(board, word): """ 使用回溯法搜索二维网格中的单词 :param board: List[List[str]], 输入的二维字符网格 :param word: str, 需要搜索的单词 :return: bool, 单词是否存在于网格中 """ def backtrack(i, j, index): if index == len(word): return True if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]: return False temp = board[i][j] board[i][j] = '#' # 标记当前格子访问过 found = (backtrack(i + 1, j, index + 1) or backtrack(i - 1, j, index + 1) or backtrack(i, j + 1, index + 1) or backtrack(i, j - 1, index + 1)) board[i][j] = temp # 回溯 return found for i in range(len(board)): for j in range(len(board[0])): if backtrack(i, j, 0): return True return False # 示例调用 print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCCED")) # 输出: true
算法分析
- 时间复杂度：(O(M * N * 4^L))，其中 (M) 和 (N) 是网格的维度，(L) 是单词的长度。每个字母有4个方向可以探索。
- 空间复杂度：(O(L))，递归的深度最大为单词长度 (L)。
方法二：深度优先搜索（DFS）+ 剪枝
解题步骤
- 深度优先搜索：类似于方法一，但增加剪枝来避免不必要的搜索，例如提前检查单词中的字符在网格中的频率。
- 优化检索：在开始搜索前，比较网格中字符的可用性和单词的需求，如果不匹配则提前返回
false。
完整的规范代码
def exist(board, word): from collections import Counter # 剪枝：先检查字符是否足够 chars = Counter(ch for row in board for ch in row) if any(word.count(c) > chars[c] for c in word): return False def dfs(i, j, k): if not (0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == word[k]): return False if k == len(word) - 1: return True board[i][j], tmp = '', board[i][j] # 避免访问自身 found = (dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)) board[i][j] = tmp return found for i in range(len(board)): for j in range(len(board[0])): if dfs(i, j, 0): return True return False # 示例调用 print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCCED")) # 输出: true
算法分析
- 时间复杂度：优化前是 (O(M * N * 4^L))，剪枝后性能有所提高但最坏情况依然是 (O(M * N * 4^L))。
- 空间复杂度：(O(L))，递归的深度最大为单词长度 (L)。
方法三：广度优先搜索（BFS）
解题步骤
- 广度优先搜索：使用队列实现层次遍历，每一层对应单词中的一个字符。
- 逐层搜索：每个位置尝试四个方向的扩展，寻找下一个字符。
完整的规范代码
def exist(board, word): from collections import deque def bfs(start): queue = deque([start]) visited = set([start]) index = 1 while queue and index < len(word): next_queue = deque() while queue: i, j = queue.popleft() for ni, nj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]: if 0 <= ni < len(board) and 0 <= nj < len(board[0]) and (ni, nj) not in visited and board[ni][nj] == word[index]: next_queue.append((ni, nj)) visited.add((ni, nj)) queue = next_queue index += 1 return index == len(word) for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == word[0] and bfs((i, j)): return True return False # 示例调用 print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCCED")) # 输出: true
算法分析
- 时间复杂度：(O(M \times N * 4^L))，尽管使用了广度优先搜索，但复杂度相当于深度优先搜索。
- 空间复杂度：(O(min(L, M * N)))，队列的最大长度取决于网格大小和单词长度的较小值。
方法四：动态规划
解题步骤
- 动态规划表达：尝试将搜索转化为动态规划问题，使用 (dp[i][j][k]) 表示从 (i, j) 开始的后缀是否可以形成 (word[k:])。
- 状态转移：根据四个方向的可能性更新状态。
完整的规范代码
def exist(board, word): m, n, l = len(board), len(board[0]), len(word) dp = [[[-1] * l for _ in range(n)] for _ in range(m)] def search(x, y, k): if k == l: return True if not (0 <= x < m and 0 <= y < n and board[x][y] == word[k]): return False if dp[x][y][k] != -1: return dp[x][y][k] board[x][y], temp = '#', board[x][y] # 避免重复使用 result = (search(x + 1, y, k + 1) or search(x - 1, y, k + 1) or search(x, y + 1, k + 1) or search(x, y - 1, k + 1)) dp[x][y][k] = result board[x][y] = temp return result for i in range(m): for j in range(n): if search(i, j, 0): return True return False # 示例调用 print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCCED")) # 输出: true
算法分析
- 时间复杂度：(O(M * N * L))，每个位置对应单词长度的状态需要计算。
- 空间复杂度：(O(M * N * L))，存储每个位置对应单词的所有状态。
方法五：库函数利用
这题目不适合直接使用库函数解决，因为它涉及到具体的路径搜索问题，不是简单的计算或数据操作。故省略此方法。
不同算法的优劣势对比
| 特征 | 方法一：回溯法 | 方法二：DFS+剪枝 | 方法三：BFS | 方法四：动态规划 | 方法五：库函数 |
| 时间复杂度 | (O(M * N * 4^L)) | (O(M * N * 4^L)) | (O(M * N * 4^L)) | (O(M * N * L)) | N/A |
| 空间复杂度 | (O(L)) | (O(L)) | (O(min(L, M * N))) | (O(M * N * L)) | N/A |
| 优势 | 灵活，直观 | 剪枝提高效率 | 层次搜索明确 | 解决重复计算问题 | 不适用 |
| 劣势 | 可能过慢 | 实现复杂 | 空间利用较大 | 空间消耗大 | 不适用 |
应用示例
游戏开发：在迷宫或解谜游戏中找到特定路径或解决方案。
图像处理：在图像识别中寻找特定模式的路径。
机器学习：在数据预处理中，从复杂的数据结构中提取特征。
欢迎关注微信公众号 数据分析螺丝钉
