题目
79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “ABCCED”
输出：true
示例 2：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “SEE”
输出：true
示例 3：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “ABCB”
输出：false
提示：
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
我的代码（Python）
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
usedSet = set()
def checkNext(currPos: (int, int), idx: int):
nonlocal board
nonlocal usedSet
nonlocal word
if idx == len(word):
return True
x, y = currPos
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or currPos in usedSet:
return False
if board[x][y] != word[idx]:
return False
usedSet.add(currPos)
result = checkNext((x - 1, y), idx + 1)
if result:
return True
result = checkNext((x + 1, y), idx + 1)
if result:
return True
result = checkNext((x, y - 1), idx + 1)
if result:
return True
result = checkNext((x, y + 1), idx + 1)
if result:
return True
usedSet.remove(currPos)
return result
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0] and checkNext((i, j), 0):
return True
return False点评
思路和官方一样，没想到要怎么剪枝，官方也没提。
虽然是能通过，但时间效率不好。
想到的一个剪枝方向，是记录每个位置当前索引是i的时候，对应的四个方向是否有查找过。
假设一个位置是b，上方和左方是a，如果从上方过来匹配到了这个位置，下方和右方继续比对；当再次从左侧匹配到这个位置的时候，右方和下方就没必要再比对了。
嫌麻烦，不做了，就这样吧😄
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog