[NeetCode 150] Search for Word

Search for Word

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Example 1:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Output: true

Example 2:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "BAT"

Output: false

Constraints:

1 <= board.length, board[i].length <= 5
1 <= word.length <= 10

board and word consists of only lowercase and uppercase English letters.

Solution

DFS and BFS are all appliable for this problem but pay attention to the constraints that each cell can only be used once. So, we need an additional 2-D array to record the cells we have passed.

Code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dir_x = [-1, 1, 0, 0]
        dir_y = [ 0, 0,-1, 1]
        vis = [[0]*len(board[0]) for _ in range(len(board))]
        def dfs(x, y, pos):
            if board[x][y] != word[pos]:
                return False
            if pos == len(word)-1:
                return True
            vis[x][y] = 1
            for i in range(len(dir_x)):
                nxt_x = x+dir_x[i]
                nxt_y = y+dir_y[i]
                if 0 <= nxt_x < len(board) and 0 <= nxt_y < len(board[0]) and vis[nxt_x][nxt_y]==0:
                    if dfs(nxt_x, nxt_y, pos+1):
                        return True
            vis[x][y] = 0
            return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False