#79 Word Search——Top 100 Liked Questions-蒲公英云

#79 Word Search——Top 100 Liked Questions

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:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

“””

第一次：深度优先搜索递归dfs
“””

class Solution(object):
    def dfs(self, board, i, j, word):
        if len(word) == 0:
            return True #全部查找到
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
            return False
        tmp = board[i][j]
        board[i][j] = '#' #为了避免重复查找，用井号代替
        res = self.dfs(board, i - 1, j, word[1: ]) or self.dfs(board, i + 1, j, word[1: ]) or self.dfs(board, i, j - 1, word[1: ]) or self.dfs(board, i, j + 1, word[1: ])
        board[i][j] = tmp
        return res
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board:
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):#从任意位置出发进行深度搜索
                if self.dfs(board, i, j, word):
                    return True  #如果能找到，返回true
        return False