79. Word Search

Question: Word Search

Solution

想法：跟走迷宮題一樣，從 (0, 0) 開始走，走到出口就 return True

board 的行與列，分別為 rows, columns: rows, columns = len(board), len(board[0])

每次從自己這格，前進到下一格的方式有 4 種：

• 上

  row - 1, column 不變

• 下

  row + 1, column 不變

• 左

  row 不變, column - 1

• 右

  row 不變, column + 1

要注意，不走來時路，所以走過的要 mark 起來，不重複 → set()

所以要準備一個 path = set() 放來時路

從第一格 (0, 0) 開始 dfs，一格一格找，每一格都是新的開始，都要從 word 的第一個字看起： for loop 兩次

for r in range(rows):

for c in range(columns):

if dfs(r, c, 0):

return True

dfs 的寫法
每一格的 index 為 r 與 c
word 的 index 為 i
終止條件
從 index 0 開始走，如果走完 word 的長度，就代表找到了： if i == len(word): return True
以下皆為 return False 的終止情況：

如果 r 跟 c 不在 rows & columns 長度範圍內

r 往上走超過頂了：r < 0
r 往下走超過底了：r ≥ rows
c 往左走超過底了：c < 0
c 往右走超過底了：c ≥ columns
如果檢查的字元，跟 board 上的字元不同： word[i] ≠ board[r][c]
如果走的是來時路：(r, c) in path
遞迴條件
word[i] == board[r][c] 時要做以下的事
把 (r, c) 放到來時路中：path.add((r, c))
檢查下一個字元 i + 1 ，並繼續往「上 or 下 or 左 or 右」走：
dfs(r + 1, c, i + 1)
dfs(r - 1, c, i + 1)
dfs(r, c + 1, i + 1)
dfs(r, c - 1, i + 1)
如果其中一個為 True 則繼續往下走
將 (r, c) 從來時路清空： path.remove((r, c))
TimeComplexity = O(m * n * dfs)
其中 dfs 會是 word 的長度
又每一格都要上下左右找四次，總共找 word 的長度次，所以 dfs = 4^len(word)
TimeComplexity = O(m * n * 4^len(word))
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, columns = len(board), len(board[0])
        path = set()
        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or
                c < 0 or 
                r >= rows or 
                c >= columns or 
                word[i] != board[r][c] or 
                (r, c) in path):
                return False
            path.add((r, c))
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            path.remove((r, c))
            return res
        for r in range(rows):
            for c in range(columns):
                if dfs(r, c, 0):
                    return True
        return False
Video Solution