# [Search]LC 79. Word Search

--

Goal

• 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`

Highlight

• Search + DFS
• 2D Matrix Search
• Search 4 directions

Strategy

• 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

Complexity

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)

Code

`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`