Mercurial

comparison grok_interview/alphabet_search.py @ 60:d64a8c189a77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged
author June Park <me@mrjunejune.com>
date Sat, 20 Dec 2025 13:56:01 -0500
parents 68fa88ac73fe
children
comparison
equal deleted inserted replaced
50:983769fba767 60:d64a8c189a77
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))