LeetCode 79 [Word Search]

原题

给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。
单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。

样例
给出board =
[
"ABCE",
"SFCS",
"ADEE"
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.

解题思路

• 遍历二维数组的每一个点，当作起始点做DFS
• 在进入DFS后，对于访问过的节点标记为None，以表明访问过
• 关于回溯要注意的是，如果返回True其实就结束了，以为已经找到答案了，也不需要回溯。如果不返回True，而是改变一个全局变量self.res的值为True，会超时

完整代码

class Solution(object):
    def __init__(self):
        self.word = ""
        
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.word = word
        for row_num in range(len(board)):
            for col_num in range(len(board[0])):
                if self.search(board, row_num, col_num, 0):
                    return True
                
        return False
        
    def search(self, board, x, y, pos):
        if self.word[pos] == board[x][y]:
            if pos == len(self.word) - 1:
                return True
            else:
                temp = board[x][y]
                board[x][y] = None
                if x + 1 < len(board) and self.search(board, x + 1, y, pos + 1):
                    return True
                if x - 1 >= 0 and self.search(board, x - 1, y, pos + 1):
                    return True
                if y + 1 < len(board[0]) and self.search(board, x, y + 1, pos + 1):
                    return True
                if y - 1 >= 0 and self.search(board, x, y - 1, pos + 1):
                    return True
                board[x][y] = temp
                return False
        else:
            return False