难度: Medium
原题连接
内容描述
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
思路 1
其实这个题和number of islands类似，是backtracking基本功的考查,但是基本功非常有待提高|||
比较核心的是dfs函数，然后这个函数有取巧的写法：如果outside of boundary就return False
loop， 如果碰到跟word开头的字母一样，把这个扔进去loop，可以考查这个char在这个board的上下左右是否可以选择，不可使用则重置used， 然后return
也还是之前摘录的，backtrack写法关键： 选择 (Options)，限制 (Restraints)，结束条件 (Termination)。
beats 93.83%
class Solution:
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board:
return False
if not word:
return True
row = len(board)
col = len(board[0]) if row else 0
def dfs(i, j, idx):
if not 0 <= i <= row - 1 or not 0 <= j <= col - 1 or board[i][j] != word[idx]:
return False
if idx == len(word) - 1:
return True
board[i][j] = '*'
res = dfs(i+1, j, idx+1) or dfs(i, j+1, idx+1) or dfs(i-1, j, idx+1) or dfs(i, j-1, idx+1)
board[i][j] = word[idx]
return res
return any(dfs(i, j, 0) for i in range(row) for j in range(col))