79. Word Search

Question: Word Search

Solution

想法：

1. 從 board 的第一個字開始找，把每個字都當成 word 的第一個字搜尋

   board[0][0] 是否等於 word[0]

   • 是，繼續找他的上下左右鄰居
     • board[0][1] 是否等於 word[1]
     • board[0][-1] 是否等於 word[1]
     • board[1][0] 是否等於 word[1]
     • board[-1][0] 是否等於 word[1]
   • 不是，看 board[0][1] 是否等於 word[0]

2. 如果 board[0][0] == word[0]，board[0][1] == word[1]，接下來要找 board[0][1] 上下左右的鄰居

   • board[0][0] 是否等於 word[2]
   • board[0][2] 是否等於 word[2]
   • board[-1][1] 是否等於 word[2]
   • board[1][1] 是否等於 word[2]

   這邊可以發現 board[0][0] 是原本已經找過的 word[0]，如果又檢查一次的話，就會走回頭路，因而重複，所以要把已經找到的路徑存起來，避免重複

   path = {(0, 0), (0, 1)}

• DFS
  • 將 board 的 row, column 假設成 r, c: board[r]c[]
• 終止條件：
  • return False
    • 上下左右找鄰居的時候，如果 index 超出範圍
      • r < 0
      • c < 0
      • r > len(row) - 1
      • c > len(column) - 1
    • 如果是來時路：(r, c) in path
    • 如果 word[i] ≠ board[r][c]
  • return True
    • 找到 word 最後一個字，且 word[i] == board[r][c] 時：i == len(word) - 1
• 遞迴條件：
• 以下任一 dfs 為 True 就繼續往下找
• 往左找
  • dfs(i + 1, r, c + 1)
• 往右找
  • dfs(i + 1, r, c - 1)
• 往上找
  • dfs(i + 1, r - 1, c)
• 往下找
• dfs(i + 1, r + 1, c)

class Solution:

def exist(self, board: list[list[str]], word: str) -> bool:

column, row = len(board[0]), len(board)

def dfs(i, r, c):

if r > len(board) - 1 or \

c > len(board[0]) - 1 or \

r < 0 or \

c < 0 or \

(r, c) in path or \

word[i] != board[r][c]:

return

elif i == len(word) - 1:

return True

path.add((r, c))

res = dfs(i + 1, r, c + 1) or \

dfs(i + 1, r, c - 1) or \

dfs(i + 1, r - 1, c) or \

dfs(i + 1, r + 1, c)

path.remove((r, c))

return res

for r in range(row):

for c in range(column):

path = set()

if dfs(0, r, c):

return True

return False

Video Solution