Word Search

题目描述

解题方法

用一个visited track走过的点，防止循环，然后找到头部就做DFS + backtracking。

Solution

class Solution(object):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board or not word:
            return False

        row_num = len(board)
        col_num = len(board[0])
        visited = [[False for i in range(col_num)] for j in range(row_num)]
        for i in range(row_num):
            for j in range(col_num):
                if board[i][j] == word[0]:
                    visited[i][j] = True
                    if self.search(board, word[1:], visited, i, j):
                        return True
                    visited[i][j] = False

        return False

    def search(self, board, word, visited, row, col):
        if len(word) == 0:
            return True
        row_num = len(board)
        col_num = len(board[0])
        for i in range(4):
            x = row + self.dx[i]
            y = col + self.dy[i]
            if x >= 0 and x < row_num and y >= 0 and y < col_num and not visited[x][y] and board[x][y] == word[0]:
                visited[x][y] = True
                if self.search(board, word[1:], visited, x, y):
                    return True
                visited[x][y] = False
        return False

Reference