Re: [閒聊] 每日leetcode已回收
GPT老師
針對單詞搜索問題，提供的程式碼片段存在幾個邏輯和結構上的問題，這些問題可能會影
響程式的正確性和效率。以下是問題的詳細審查以及如何解決這些問題以改善程式碼：
每次DFS呼叫重新初始化visited：visited列表在不同的起始點和遞迴DFS呼叫中共享，這
可能會導致不正確的行為，因為對於一個新的起始點來說，應該有效的路徑可能會由於從
之前搜索中留下的狀態被認為是無效的。
在DFS中修改visited：visited列表通過追加訪問過的節點來修改。然而，在回溯時，它
沒有從visited中移除節點，導致路徑跟踪不正確。
檢查visited的效率：使用列表作為visited導致效率低下的檢查（if (x, y) in visited
）。使用集合來進行常數時間的查找更好。
變量的範疇：變量m和n的指派不正確。正確的指派應該是m = len(board)和n = len(
board[0])，因為m通常代表矩陣中的行數，而n代表列數。
DFS的早期返回：如果DFS函數找不到單詞，應該返回False，以確保在確定單詞不存在於
板上之前探索所有路徑。
DFS呼叫覆蓋：DFS呼叫沒有處理導致解決方案的路徑不正確繼續搜索而沒有適當回溯的情
況。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board or not board[0]:
return False
m, n = len(board), len(board[0])
def dfs(x, y, index, visited):
if index == len(word):
return True
if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != word[index
] or (x, y) in visited:
return False
visited.add((x, y))
res = (dfs(x + 1, y, index + 1, visited) or
dfs(x - 1, y, index + 1, visited) or
dfs(x, y + 1, index + 1, visited) or
dfs(x, y - 1, index + 1, visited))
visited.remove((x, y))
return res
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
if dfs(i, j, 0, set()):
return True
return False
Key improvements:
Introduced a set for visited to efficiently track visited cells.
Correctly reassigned m and n to match the matrix dimensions.
Implemented backtracking by adding and removing from visited within the DFS.
Ensured that all directions are explored, and only terminate early if the word
is found.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.26.18.152 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712138097.A.A31.html
推
04/03 17:55,
1年前
, 1F
04/03 17:55, 1F
→
04/03 17:55,
1年前
, 2F
04/03 17:55, 2F
※ 編輯: HGK (114.26.18.152 臺灣), 04/03/2024 17:58:34
推
04/03 18:09,
1年前
, 3F
04/03 18:09, 3F
討論串 (同標題文章)
完整討論串 (本文為第 90 之 1548 篇)：