Word Search

Question

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.

Have you met this question in a real interview? Yes Example Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

Thoughts

找到与第一个字母相同的地方，然后做dfs 在dfs的过程中用一个matrix保存visit过的点，防止循环 在这个character check过了之后将visited设为False

ref

Solution

class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        # write your code here
        row = len(board)
        if not row:
            return False
        col = len(board[0])
        self.visited = [[False for x in range(len(board[0]))] for y in range(len(board))]
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0] and self.dfs(board, word, i, j, 0):
                    return True

        return False


    def dfs(self, board, word, i, j, index):
        if index == len(word) - 1:
            return True


        self.visited[i][j] = True

        # check 3 status:
        # 1. in bound
        # 2. char match
        # 3. unvisited


        #up
        if i - 1 >= 0 and board[i-1][j] == word[index+1] and self.visited[i-1][j] == False:
            if self.dfs(board, word, i - 1, j, index + 1):
                return True

        #down
        if i + 1 <= len(board) - 1 and board[i+1][j] == word[index+1] and self.visited[i+1][j] == False:
            if self.dfs(board, word, i + 1, j, index + 1):
                return True

        #left
        if j - 1 >= 0 and board[i][j-1] == word[index+1] and self.visited[i][j-1] == False:
            if self.dfs(board, word, i, j - 1, index + 1):
                return True

        #right
        if j + 1 <= len(board[0]) - 1 and board[i][j+1] == word[index+1] and self.visited[i][j+1] == False:
            if self.dfs(board, word, i, j+1, index + 1):
                return True

        self.visited[i][j] = False

        return False