Jianbo Dai's

mq052.单词搜索

 
  • Jan 18, 2021

题目链接

继续回溯法，有个小技巧就是用if helper(): return True 而非直接使用return helper()，否则会因为虽然一开始进入了helper函数而后续的要求没满足导致直接返回结果，实际上还有其他符合helper函数的条件要在比较完后续的之后才能下结论，不这样处理就错了。算法的时间复杂度有个宽松的上界是O（MN3**L），M和N分别是矩阵的长宽，L是word的长度，由于剪枝的存在所以时间复杂度不会这么大。空间复杂度是O（NM），我们额外开辟了visited数组。

python:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        lrow, lcol = len(board), len(board[0])
        visited = [[False]*lcol for _ in range(lrow)]
        
        def helper(x, y, index, visited):
            if index == len(word):
                return True
            ds = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            cur = word[index]
            for d in ds:
                new_x, new_y = x + d[0], y + d[1]
                if 0 <= new_x < lrow and 0 <= new_y < lcol and not visited[new_x][new_y]:
                    if board[new_x][new_y] == cur:
                        visited[new_x][new_y] = True
                        if helper(new_x, new_y, index+1, visited):
                            return True
                        visited[new_x][new_y] = False
            return False

        for i in range(lrow):
            for j in range(lcol):
                if board[i][j] == word[0]:
                    visited[i][j] = True
                    if helper(i, j, 1, visited):
                        return True
                    visited[i][j] = False
    
        return False
Search