79. 单词搜索 [medium]

https://leetcode-cn.com/problems/word-search/

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

通过次数73,177 | 提交次数173,574

First Try

2020-07-29

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 其实如果要多次使用，较快的方法肯定还是对矩形的所有可能构建trie树
        # 既然是一次性的，那就还是backtrack来一波吧 
        if not (len(board) and len(board[0]) and len(word)):
            return False 

        m, n = len(board), len(board[0])
        
        def backtrack(i, j, fidx, visited):
            if fidx == len(word):
                return True 
            for si, sj in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                nsi, nsj = i + si, j + sj 
                if 0 <= nsi < m and 0 <= nsj < n \
                    and (nsi, nsj) not in visited \
                    and board[nsi][nsj] == word[fidx]:
                    visited.add((nsi, nsj))
                    if backtrack(nsi, nsj, fidx + 1, visited):
                        return True 
                    visited.remove((nsi, nsj))
            return False 
            
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    if backtrack(i, j, 1, set([(i, j)])):
                        return True 
        return False 

执行用时：352 ms, 在所有 Python3 提交中击败了15.65%的用户
内存消耗：14.7 MB, 在所有 Python3 提交中击败了11.11%的用户

79. 单词搜索 [medium]​

First Try​

79. 单词搜索 [medium]

First Try