Description

Given a 2D board and a word, find if the word exists in the grid.

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

Example:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solutions

  题意很直接,给你一个字母数组和一个单词,问单词是否可以由字符数组中相邻字母拼接起来,并且每个单词只能被用一次。

  这里不能用回溯,因为每个单词只能备用一次。可以看到之前用 Backtracking 做一直在超时。这里也最好用 DFS,因为长度固定,而且也不会特别长。

  用 Backtracking 就一直没有 AC,发现原来是没有防止重复访问,以及当只有一个元素的时候循环不会执行,因为我把边界判断放到了循环里,修改之后还是 TLE。

# Time: O()
# Space: O()
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or len(board) == 0:
            return False
        r, c = len(board), len(board[0])
        for i in range(r):
            for j in range(c):
                if self.dfs(board, word, r, c, i, j):
                    return True
        return False
    
    def dfs(self, board, remain, r, c, i, j):
        if remain == '':
            return True
        if i < 0 or i >= r or j < 0 or j >= c or board[i][j] != remain[0]:
            return False
        # for x, y in {(i+1, j), (i-1, j), (i, j-1), (i, j+1)}:
        for x, y in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
            tmp = board[i][j]
            board[i][j] = '#'
            if self.dfs(board, remain[1:], r, c, x, y):
                board[i][j] = tmp
                return True
            board[i][j] = tmp
        return False
# Time Limit Exceeded

  发现原来是因为我在写反向的时候用的不是 [] 而是 {}

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

    def dfs(self, board, word, i, j, r, c):
        if not word:
            return True
        if not (0 <= i < r) or not (0 <= j < c) or word[0] != board[i][j]:
            return False
        tmp = board[i][j]
        board[i][j] = '#'
        res = self.dfs(board, word[1:], i + 1, j, r, c) or \
                self.dfs(board, word[1:], i - 1, j, r, c) or \
                self.dfs(board, word[1:], i, j + 1, r, c) or \
                self.dfs(board, word[1:], i, j - 1, r, c)
        board[i][j] = tmp
        return res
# Runtime: 356 ms, faster than 69.16% 
# Memory Usage: 13.7 MB, less than 100.00% 

References

  1. 79. Word Search