当前位置：首页 > news >正文

力扣刷题Day 65：单词搜索（79）

news 2025/6/1 13:21:55

1.题目描述

2.思路

方法1（自己写的深度优先的回溯方法）：遍历网格，每走过一格都将其坐标加入visited集合，然后向上、下、左、右四个方向查找可行路径，如果找到可行路径则一路向下延伸查找，如不可行则将该坐标从集合里删除，回退到上一坐标继续查找。

方法2（参考Krahets佬的题解对方法1进行了优化）：无需用tmp记录当前字符串，直接简化为记录当前字符串长度即可，可进一步节省空间（字符串tmp->整数k）与时间（startswith比较字符串->比较指定坐标的一个字符）。

3.代码（Python3）

方法1：

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def backtrack(tmp, i, j):print(tmp, i, j)if tmp == word: return Truefor (move_m, move_n) in {(-1, 0), (1, 0), (0, -1), (0, 1)}:if 0 <= i + move_m < m and 0 <= j + move_n < n and word.startswith(tmp + board[i][j]):tmp += board[i][j]if backtrack(tmp, i + move_m, j + move_n): return Truereturn Falsem, n= len(board), len(board[0])for i in range(m):for j in range(n):if board[i][j] == word[0]:return backtrack(board[i][j], i, j)return False

方法2：

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def backtrack(k, i, j):visited.add((i, j))if k == len(word) - 1: return Truefor (move_m, move_n) in {(-1, 0), (1, 0), (0, -1), (0, 1)}:if 0 <= i + move_m < m and 0 <= j + move_n < n and (i + move_m, j + move_n) not in visited and word[k + 1] == board[i + move_m][j + move_n]:if backtrack(k + 1, i + move_m, j + move_n): return Truevisited.discard((i, j))return Falsem, n = len(board), len(board[0])visited = set()for i in range(m):for j in range(n):if board[i][j] == word[0]:if backtrack(0, i, j): return Truereturn False