KK's blog

每天积累多一些

0%

LeetCode 079 Word Search

Posted on Edited on Disqus:

LeetCode



Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true


Example 2:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
Output: true


Example 3:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
Output: false


Constraints:

m == board.length n = board[i].length
1 <= m, n <= 6 1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

*Follow up: Could you use search pruning to make your solution faster with a larger board?

算法思路：

N/A

注意事项：

  1. 难点在于判断不合法情况的顺序，比DFS模板稍复杂。这些语句都在for循环外，按此顺序： word_index和(start_x, start_y)不合法，该点访问过(模板)，字母不等。
    然后visited为True，循环后visited为False
    根据DFS模板visited紧接在return之后(当然先确保不越界)，visited赋值一定要在所有不合法情况之后，不能紧跟visited比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
OFFSETS = [(0, 1), (1, 0), (-1, 0), (0, -1)]
class Solution(TestCases):

    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0] or not word:
            return False
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, i, j, word, 0, visited):
                    return True
        return False

    def dfs(self, board, start_x, start_y, word, word_index, visited):
        if word_index >= len(word):
            return True
        if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
            return False
        if visited[start_x][start_y]:
            return False
        if board[start_x][start_y] != word[word_index]:
            return False
        visited[start_x][start_y] = True
        for dx, dy in OFFSETS:
            if self.dfs(board, start_x + dx, start_y + dy, word, word_index + 1, visited):
                return True
        visited[start_x][start_y] = False
        return False

算法分析：

时间复杂度为O(n2*3L)，空间复杂度O(n2), n是矩阵长度，L是最大单词长度.
3是因为访问过的节点不合法，也就是来的节点不能再走一次，所以只能3个方向

Free mock interview