Jianbo Dai's

lc079.单词搜索

 
  • May 23, 2020

单词搜索

这题与矩阵中的路径相同。另外补充一下一个比较常见的

这个算法的时间复杂度是$O（3^KMN）$，K，M，N分别为word的长度和矩阵的两个维度，MN是因为第一个字符有可能需要遍历矩阵的每个位置，3的K次是因为在从第二个字符开始，其每次搜索都只需要搜索3个位置甚至更少。空间复杂度取决于递归深度，是O（K）。

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