182 - 79 单词搜索

题目

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

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

示例:

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

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

解答

感觉可以回溯，但不知道怎么找第一个字母。走过的路可以直接覆盖掉原来的board。

回溯

https://leetcode-cn.com/problems/word-search/solution/hui-su-dfs-by-powcai/

他的意思是，直接用递归，遇到错的就减枝。也不用管第一个字母在哪，就从左上角算到右下角😂

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not word:
            return False
        row = len(board)
        col = len(board[0])
        direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        def backtrack(i, j, target, visited):
            if target == len(word):
                return True
            for x, y in direction:
                tmp_i, tmp_j = x+i, y+j
                if 0 <= tmp_i and tmp_i < row and 0 <= tmp_j and tmp_j < col\
                        and (tmp_i, tmp_j) not in visited and board[tmp_i][tmp_j] == word[target]:
                    visited.add((tmp_i, tmp_j))
                    if backtrack(tmp_i, tmp_j, target+1, visited):
                        return True
                    visited.remove((tmp_i, tmp_j))
            return False

        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0] and backtrack(i, j, 1, {(i, j)}):
                    return True
        return False

Runtime: 296 ms, faster than 90.55% of Python3 online submissions for Word Search.

Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Word Search.

原地算法

https://leetcode-cn.com/problems/word-search/solution/dfs-yuan-ju-zhen-zhong-xiu-gai-by-liyiping/

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not word:
            return False
        row = len(board)
        col = len(board[0])

        def backtrack(x, y, target, board):
            if x < 0 or x == row or y < 0 or y == col:
                return False
            if board[x][y] == "#" or board[x][y] != word[target]:
                return False
            if target == len(word)-1:
                return True
            tmp = board[x][y]
            board[x][y] = "#"
            flag = backtrack(x-1, y, target+1, board)\
                or backtrack(x+1, y, target+1, board)\
                or backtrack(x, y-1, target+1, board)\
                or backtrack(x, y+1, target+1, board)
            board[x][y] = tmp
            return flag

        for i in range(row):
            for j in range(col):
                if backtrack(i, j, 0, board):
                    return True
        return False

Runtime: 312 ms, faster than 86.85% of Python3 online submissions for Word Search.

Memory Usage: 14 MB, less than 95.74% of Python3 online submissions for Word Search.