Word search#

Levels: level-4

Data structures: array

Patterns: backtracking

Practice Link#

Description#

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.

Example#

 1board =
 2[
 3  ['A','B','C','E'],
 4  ['S','F','C','S'],
 5  ['A','D','E','E']
 6]
 7
 8Given word = "ABCCED", return true.
 9Given word = "SEE", return true.
10Given word = "ABCB", return false.

Constraints:

Board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

Python Solution#

 1class Solution(object):
 2    def exist(self, board, word):
 3        """
 4        :type board: List[List[str]]
 5        :type word: str
 6        :rtype: bool
 7        """
 8        if not board:
 9            return False
10        for i in range(len(board)):
11            for j in range(len(board[0])):
12                if self.dfs(board, i, j, word):
13                    return True
14        return False
15
16    # check whether can find word, start at (i,j) position
17    def dfs(self, board, i, j, word):
18        if len(word) == 0:  # all the characters are checked
19            return True
20        if i < 0 or i >= len(board) or j < 0 or j >= len(
21                board[0]) or word[0] != board[i][j]:
22            return False
23        tmp = board[i][j]  # first character is found, check the remaining part
24        board[i][j] = "#"  # avoid visit agian
25        # check whether can find "word" along one direction
26        res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
27        or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
28        board[i][j] = tmp
29        return res