[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