79.md

题目地址

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

解答1

class Solution:
    visit = [[]]
    direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    def exist(self, board: List[List[str]], word: str) -> bool:
        """
            单词搜索(非最优解)

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

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

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

            给定 word = "ABCCED", 返回 true.
            给定 word = "SEE", 返回 true.
            给定 word = "ABCB", 返回 false.
        """
        row, col = len(board), len(board[0])
        if not row:
            return False
        if not word:
            return True
        if row * col < len(word):
            return False

        self.visit = [[False for i in range(col)] for j in range(row)]
        for i in range(row):
            for j in range(col):
                if word[0] == board[i][j]:
                    if self.dfs(i, j, board, word, 1):
                        return True
        return False

    def dfs(self, i, j, board, word, key):
        if key == len(word):
            return True
        self.visit[i][j] = True
        row, col = len(board), len(board[0])
        for direct in self.direction:
            x, y = i + direct[0], j + direct[1]
            if x < 0 or y < 0 or x >= row or y >= col or self.visit[x][y]:
                continue
            if board[x][y] == word[key] and self.dfs(x, y, board, word, key + 1):
                return True
            else:  # 这个路径不通
                continue

        self.visit[i][j] = False
        return False

解答2

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """
            单词搜索(非最优解)

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

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

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

            给定 word = "ABCCED", 返回 true.
            给定 word = "SEE", 返回 true.
            给定 word = "ABCB", 返回 false.
        """
        m, n, l = len(board), len(board[0]), len(word)
        # b is complex number board
        b = {i + 1j * j: board[i][j] for i in range(m) for j in range(n)}

        # backtrack
        def findWord(z, w):
            if not w:
                self.ans += 1;
                return
            else:
                for k in range(4):
                    c = z + 1j ** (k + 1)
                    if not self.ans and c in b and b[c] == w[0]:
                        b[c] = ''
                        findWord(c, w[1:])
                        b[c] = w[0]

        self.ans = 0
        for z in b.keys():
            if b[z] == word[0]:
                b[z] = ''
                findWord(z, word[1:])
                if self.ans > 0: return True
                b[z] = word[0]

        return False

解答3

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """
            单词搜索

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

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

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

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

        def preCheck():
            preDict = {}

            for i in word:
                if i in preDict:
                    preDict[i] += 1
                else:
                    preDict[i] = 1

            for i in board:
                for j in i:
                    if j in preDict and preDict[j] > 0: preDict[j] -= 1
            for i in preDict.values():
                if i > 0: return False
            return True

        def helper(wordIdx, x, y):
            if board[x][y] != word[wordIdx]:
                return False
            elif wordIdx == l - 1:
                return True
            else:
                wordIdx += 1
                tempChar = board[x][y]
                board[x][y] = None
                for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    xNext = x + d[0]
                    yNext = y + d[1]
                    if -1 < xNext < m and -1 < yNext < n and board[xNext][yNext]:
                        if helper(wordIdx, xNext, yNext): return True
                board[x][y] = tempChar
                return False

        if not board: return False
        if not word: return True

        if not preCheck(): return False

        m = len(board)
        n = len(board[0])
        l = len(word)
        for i in range(m):
            for j in range(n):
                if helper(0, i, j): return True

        return False