|
69
|
1 # Given an m x n grid of characters board and a string word, return true if word exists in the grid.
|
|
|
2 #
|
|
|
3 # The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
|
|
|
4 #
|
|
|
5 #
|
|
|
6 #
|
|
|
7 # Example 1:
|
|
|
8 #
|
|
|
9 #
|
|
|
10 # Input: board = [
|
|
|
11 # ["A","B","C","E"],
|
|
|
12 # ["S","F","C","S"],
|
|
|
13 # ["A","D","E","E"]
|
|
|
14 # ], word = "ABCCED"
|
|
|
15 # Output: true
|
|
|
16
|
|
|
17 def main(board, word):
|
|
|
18 ROWS = len(board)
|
|
|
19 COLS = len(board[0])
|
|
|
20
|
|
|
21 pos = 0
|
|
|
22
|
|
|
23 directions = [
|
|
|
24 (0, 1),
|
|
|
25 (1, 0),
|
|
|
26 (0, -1),
|
|
|
27 (-1, 0),
|
|
|
28 ]
|
|
|
29 def dfs(row, col, pos):
|
|
|
30 # import pdb; pdb.set_trace()
|
|
|
31 if pos == len(word):
|
|
|
32 return True
|
|
|
33
|
|
|
34 if (row < 0 or row >= ROWS) or (col < 0 or col >= COLS) or board[row][col] == "#":
|
|
|
35 return False
|
|
|
36
|
|
|
37 letter = board[row][col]
|
|
|
38 if letter == word[pos]:
|
|
|
39 pos += 1
|
|
|
40 board[row][col] = "#"
|
|
|
41 for direction in directions:
|
|
|
42 if dfs(row + direction[0], col + direction[1], pos):
|
|
|
43 return True
|
|
|
44 board[row][col] = letter
|
|
|
45
|
|
|
46 for r in range(ROWS):
|
|
|
47 for c in range(COLS):
|
|
|
48 if dfs(r, c, 0):
|
|
|
49 return True
|
|
|
50 return False
|
|
|
51
|
|
|
52
|
|
|
53 board = [["b"],["a"],["b"],["b"],["a"]]
|
|
|
54 word = "baa"
|
|
|
55
|
|
|
56 print(main(board, word))
|
