python实现leetcode之79. 单词搜索

解题思路

不断搜索单词的后缀
或者单词搜索完，返回True
或者无路可走，周围都被搜索过，返回False

79. 单词搜索

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        marked = [[0 for col in row] for row in board]
        for i in range(len(board)):
            for j in range(len(board[i])):
                if emit(board, marked, word, i, j):
                    return True
        return False


def emit(matrix, trace, wd, row, col):
    if wd[0] != matrix[row][col]: return False  # 当前不匹配
    if len(wd) == 1: return True  # 完全匹配
    trace[row][col] = 1
    for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        x = row + d[0]
        y = col + d[1]
        if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):
            if not trace[x][y] and emit(matrix, trace, wd[1:], x, y):
                return True
    trace[row][col] = 0
    return False