【Leetcode 筆記】79. Word Search

題目解釋

給定一個 m x n board 的 grid 和一個字串 word，如果 word 存在於 grid 中，則傳回 true。

該單字可以由順序相鄰的單元格的字母構成，其中相鄰的單元格水平或垂直相鄰。同一字母單元不得使用多次。

範例

• 輸入: board = [["A", "B", "C", "E"],["S", "F", "C", "S"],["A", "D", "E", "E"]], word = "ABCCED"
• 輸出: True

最佳解法

套用 圖 + dfs 的模板解決。

path 用來記錄走過的 row 跟 col 組合，
而 word 的字母則固定寫在遞迴呼叫的裡面，
因為我們要在上下左右四個方向尋找 i+1 的位置的字母才可以說 board 裡面有 word。

此外要注意的就是 boundry condition 內除了處理常規的防越界之外，
還要加上 (board

接下來，每個 row 跟 col 都從 word[0] 開始尋找，找到了再 return True。

程式碼

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

        def _dfs(row, col, i):
            if i == len(word):
                return True
            if (row < 0) or (col < 0) or (row >= ROWS) or (col >= COLS) or \
                (board

	

				

			
					
					

	 != word[i]) or ((row, col) in path):
                return False
            else:
                path.add((row, col))
                res = (
                    _dfs(row - 1, col, i + 1) or \
                    _dfs(row + 1, col, i + 1) or \
                    _dfs(row, col - 1, i + 1) or \
                    _dfs(row, col + 1, i + 1)
                )
                path.remove((row, col))
                return res

        for row in range(ROWS):
            for col in range(COLS):
                if _dfs(row, col, 0):
                    return True

        return False

時間複雜度

O(r * c * 4s)，r 跟 c 分別是 board 的 cols 跟 rows 數，
而 s 是 word 的長度，每次都走上下左右。

空間複雜度

O(s)，s 是 word 的長度，只會有 s 組的 paths。

結語

高頻題，務必好好把握❗

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26