題目介紹:
給定一個 m × n 的字母矩陣 board 和一個字串 word,判斷 word 是否存在於矩陣中。字串可以從任意位置的字母開始,水平或垂直相鄰的字母連續拼接形成,且每個單元格 只能使用一次。如果矩陣中存在該字串,返回true,否則返回 false。
解題流程:
1.遍歷矩陣,每個格子作為起點嘗試匹配字串
2.使用 DFS(深度優先搜尋)或回溯法,沿水平和垂直方向搜尋下一個字母
3.搜尋過程中標記已使用的格子,避免重複使用
4.若整個字串匹配完成,返回 true;若所有起點都失敗,返回 false
程式碼及執行結果截圖:
學習心得:
透過從矩陣中每個格子出發,遞迴探索四個方向,我學會了如何在複雜結構中進行系統化搜尋。同時,使用 visited 或暫時修改格子狀態避免重複使用,讓我體會到回溯法在限制條件下的靈活性。這題也強化了我對邊界條件檢查的重要性,例如避免索引越界或重複訪問。完成這題後,我發現 DFS 不僅適合樹或圖,也能有效處理二維矩陣字串搜尋問題,為未來解決類似問題打下扎實基礎。
延伸邏輯時事面:
1.迷宮與路徑搜尋應用:DFS 與回溯法不僅可用於字串搜尋,也可應用在迷宮、棋盤遊戲、地圖路徑規劃等問題,幫助解決尋路或最短路徑問題。
2.AI 拼圖與文字遊戲:像 Scrabble、Boggle 或文字方塊遊戲,都需要搜尋矩陣內符合規則的單詞,這題的 DFS 搜尋邏輯正是底層核心。
3.數據分析與圖像識別:在圖像或網格資料中,尋找特定模式或結構(如像素組成的形狀、病毒分布路徑等)也可用 DFS 回溯,這與字母矩陣中尋找單詞類似,具有現實應用價值。