題目出處
難度
medium
題目分類
Array, String, Backtracking, Depth-First Search, Matrix
2026-10-12 三刷
個人範例程式碼 - 三刷 (2026/10/12)
class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(i, j, visited, word_idx):
if i < 0 or m <= i or j < 0 or n <= j or \
board[i][j] != word[word_idx] or \
(i, j) in visited:
return False
if word_idx == len(word)-1:
return True
visited.add((i, j))
for di, dj in directions:
if dfs(i+di, j+dj, visited, word_idx+1):
return True # found
visited.remove((i, j)) # backtracking
return False # not found
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
if dfs(i, j, set(), 0):
return True
return False
算法說明
大致可以拆成兩部分：起點搜尋、表格內搜尋。
- 起點搜尋：找到起始單字
- 表格內搜尋：根據上下左右進行 DFS 搜尋，留意重複(透過 visited 排除)，留意 backtracking。
Time Complexity
O(mn3^L)
- m*n：起點搜尋
- 3^L：三個方向，扣掉來的方向 (會在 visited 裡面)
Space Complexity
O(L) # stack 裡面最長存字串長度
2026-09-30 二刷
個人範例程式碼 - 二刷 (2026/09/30)
class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
h, w = len(board), len(board[0])
def dfs(r, c, word_idx, visited):
if word_idx == len(word):
return True
if not (0 <= r < h) or not (0 <= c < w) or \
(r, c) in visited or board[r][c] != word[word_idx]:
return False
visited.add((r, c))
res = dfs(r+1, c, word_idx+1, visited) or \
dfs(r-1, c, word_idx+1, visited) or \
dfs(r, c+1, word_idx+1, visited) or \
dfs(r, c-1, word_idx+1, visited)
visited.remove((r, c)) # backtracking 先走錯分支回來再走, 要先刪除
return res
# find first word
for r in range(h):
for c in range(w):
if board[r][c] == word[0] and \
dfs(r, c, 0, set()):
return True
return False
算法說明
- DFS # 深度搜尋 與
- backtracking # 記得每次回頭要移除已經看過的路徑
的綜合題目
這題算是經典題型，找到第一個字之後進 DFS 進行上下左右搜尋，並用 visited 紀錄已經走過的路徑。
Time Complexity
O(mn*4^L)
- mn：矩陣大小，每格都要看
- 4^L：L 是文字長度，4 是 4 個方向，4^L 「表示每一個文字的 4 個方向都看的計算時間」 (再優化可以到 3^L，扣到來的方向)
Space Complexity
O(L) # 遞回最深就是文字 L 的長度
2022-04-27 一刷
個人範例程式碼 - 一刷 (2022/04/27)
DIRECTIONS = [
(1, 0),
(-1, 0),
(0, 1),
(0, -1)
]
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board:
return False
# first point
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0] and self.dfs(board, word[1:], i, j, {(i,j)}):
return True
return False # after all search
def dfs(self, board, word, i, j, visited):
# end of recursion
if not word:
return True
# define and split
for (dx, dy) in DIRECTIONS:
next_x, next_y = i+dx, j+dy
# print(next_point)
if self.is_valid_point(next_x, next_y, board, visited, word[0]):
visited.add((next_x, next_y))
if self.dfs(board, word[1:], next_x, next_y, visited):
return True
visited.remove((next_x, next_y)) # backtracking
return False
# def dfs(self, board, word, start_point, visited)
# # end of recursion
# if not word
# return True
# # define and split
# for (dx, dy) in DIRECTIONS
# next_point = (start_point[0]+dx, start_point[1]+dy)
# # print(next_point)
# if self.is_valid_point(next_point, board, visited, word[0])
# visited.add(next_point)
# if self.dfs(board, word[1:], next_point, visited)
# return True
# visited.remove(next_point) # backtracking
# return False
def is_valid_point(self, x, y, board, visited, word):
if (x, y) in visited:
return False
r = len(board)
c = len(board[0])
return 0 <= x < r and 0 <= y < c and board[x][y] == word
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
這題是學習矩陣內的四方向搜尋，類似題目可參考：
不過這題目有個難點是很容易 TLE，在處理上我們需要稍微優化一下：
優化比較的項目長度
例如說可能不要比較整個 prefix，而是只比較單一個 word
不要使用 tuple 實作
我註解掉的部分是使用 tuple 實作的，概念上應該會更清楚，
但因為會影響到時間，後來取消掉註解後才沒有 TLE
input handling
當沒有 matrix 時，return False
Boundary conditions
搜尋到目標後，就可以 return True 了。
沿路上發現字母不對，就直接 return False