[Search]LC 79. Word Search

Iris S
2 min readSep 3, 2021



  • 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


Time: O(x*y*4^n), with n = length of word, x=row, y = col; since we visit 4 directions and we have to reach the end of the target word

Space: O(x*y*n)


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