[Search]LC 79. Word Search

  • Given an m x n grid of characters board and a string word, return true if word exists in the grid.
  • 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.
  • Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
  • Search + DFS
  • 2D Matrix Search
  • Search 4 directions
  • Use a nested for loop to visit every cell in the board
  • Perform DFS in each cell!
  • To make sure we only visit the target word one time, we can mark the visited cells as 0 during each DFS call, and toggle the value back at the end
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:

def search(row, col, idx):
if row < 0 or col < 0 or row == x or col ==y or board[row][col] != word[idx]:
return False
if idx == target:
return True

temp = board[row][col]
board[row][col] = 0

found = search(row+1, col, idx+1) or search(row-1, col, idx+1) or search(row, col+1, idx+1) or search(row, col-1, idx+1)
board[row][col] = temp

return found

x = len(board)
y = len(board[0])
target = len(word)-1

for i in range(x):
for j in range(y):
if search(i,j,0):
return True
return False

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store