Search for Word
Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.
For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.
Example 1:
Input:
board = [["A","B","C","D"],["S","A","A","T"],["A","C","A","E"]
],
word = "CAT"Output: true
Example 2:
Input:
board = [["A","B","C","D"],["S","A","A","T"],["A","C","A","E"]
],
word = "BAT"Output: false
Constraints:
1 <= board.length, board[i].length <= 5
1 <= word.length <= 10
board and word consists of only lowercase and uppercase English letters.
Solution
DFS and BFS are all appliable for this problem but pay attention to the constraints that each cell can only be used once. So, we need an additional 2-D array to record the cells we have passed.
Code
class Solution:def exist(self, board: List[List[str]], word: str) -> bool:dir_x = [-1, 1, 0, 0]dir_y = [ 0, 0,-1, 1]vis = [[0]*len(board[0]) for _ in range(len(board))]def dfs(x, y, pos):if board[x][y] != word[pos]:return Falseif pos == len(word)-1:return Truevis[x][y] = 1for i in range(len(dir_x)):nxt_x = x+dir_x[i]nxt_y = y+dir_y[i]if 0 <= nxt_x < len(board) and 0 <= nxt_y < len(board[0]) and vis[nxt_x][nxt_y]==0:if dfs(nxt_x, nxt_y, pos+1):return Truevis[x][y] = 0return Falsefor i in range(len(board)):for j in range(len(board[0])):if dfs(i, j, 0):return Truereturn False