# **Leetcode筆記(Word Search)**

:::info
:information_source: 題目 : Word Search, 類型 : graph , 等級 : medium
日期 : 2023/03/02，2023/05/17，2023/07/11，2023/12/01，2024/04/04，2025/02/20
:::

### 嘗試

2023/05/17，判斷錯誤條件要放上面

条件判断顺序错误：在 dfs 函数中，你应该首先检查边界条件，
然后再检查字符匹配和访问状态。
将边界条件判断放在了字符匹配判断之后，
这会导致出现越界或访问重复位置的情况。
錯誤 : if board[r][c] != word[i] or r < 0 or r >= m 
        or c < 0 or c >= n or (r, c) in visited

    

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        visited = set()

        def dfs(r, c, i):
            if i == len(word):
                return True
            # 條件不符
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i] or (r, c) in visited:
                return False
            
            visited.add((r, c))

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                # 如果把r和c的範圍限制條件放在這裡
                # 會使得board = "a", word = "a"這種例子無法通過
                # 但如果放上面進到i == len(word)就會通過了
                if dfs(nr, nc, i + 1):
                    return True

            # 會跑到這邊就代表dfs沒有回傳True
            # 要回頭是其他條路
            visited.remove((r, c))
            return False


        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        return False

2023/07/11
需要**在遞迴呼叫dfs()時，加上if dfs()，因為如果其中一個一層達成上面return True的條件，那後面在遞迴stack的 皆無條件return True**
最後**如果這條路徑走不通，那就需要remove((r, c))，如果有兩層以上的遞迴路徑，remove會使得退回上一層時，visited內裝的是正常的路徑**

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()

        def dfs(r, c, i, visited):
            if i == len(word):
                return True

            if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] != word[i] or (r, c) in visited:
                return
            
            visited.add((r, c))

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                # 如果其中一個一層達成上面return True的條件
                # 那後面在遞迴stack的 皆無條件return True
                if dfs(nr, nc, i + 1, visited): 
                    return True 

            visited.remove((r, c))

            return

        for r in range(len(board)):
            for c in range(len(board[0])):
                if dfs(r, c, 0, visited):
                    return True
        return False

2023/12/01

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n, m = len(board), len(board[0])
        visited = set()
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited or board[r][c] != word[i]:
                return False
            
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if dfs(nr, nc, i + 1):
                    return True
            
            visited.remove((r, c))
            return False

        for r in range(n):
            for c in range(m):
                if dfs(r, c, 0):
                    return True
        return False

2024/04/04

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = set()
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or (r, c) in visited or board[r][c] != word[i]:
                return False
            
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if dfs(nr, nc, i + 1):
                    return True
            
            visited.remove((r, c))
            return


        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        
        return False

2025/02/20

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.n, self.m = len(board), len(board[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.visited = set()
        self.board, self.word = board, word

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(r, c, 0):
                    return True
        return False

    def dfs(self, r, c, i):
        if i == len(self.word):
            return True
        if r < 0 or r >= self.n or c < 0 or c >= self.m or self.board[r][c] != self.word[i] or (r, c) in self.visited:
            return
        
        self.visited.add((r, c))
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            if self.dfs(nr, nc, i + 1):
                return True
        
        self.visited.remove((r, c))
        return

---
### **優化**

時間複雜度：
- 在最壞的情況下，我們需要遍歷整個二維字符矩陣，因此時間複雜度為 O(rows * cols)，其中 rows 是矩陣的行數，cols 是矩陣的列數。
- 在每個遍歷過程中，我們可能需要遞迴調用 `dfs` 函數，該函數的時間複雜度與單詞長度相關，即 O(word_length)。
- **總體時間複雜度為 O(rows * cols * word_length)**。

空間複雜度：
- **在最壞的情況下(當word等於整個matrix上面的所有數字)**，當遞迴深度達到最大值時，堆疊空間的最大需求是 O(rows * cols)。
- `visited` 集合用於記錄已訪問的位置，其大小取決於二維字符矩陣的大小，最大情況下是 O(rows * cols)。
- 總體空間複雜度為 O(rows * cols)。

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

        def dfs(r, c, i): # i為word中第幾個
            if i == len(word):
                return True
            
            if (r < 0 or c < 0 or r >= row or c >= col or 
            word[i] != board[r][c] or # 字母對不上
            (r, c) in path): # 已找到過
                return False # 也可以只打return(也就是return None)
                # 跳回呼叫它的起點

            path.add((r, c)) # 開始找到第一個會經過這裡

            # 若有任一一個dfs()執行，則res會收到true
            res = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or 
            dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))

            # 上面找到的那點鄰近都沒有下一個點 代表不是真正的正確點 
            path.remove((r, c)) 
            return res # True或False
            # 如果是False 則會回去下面 跑下一個迴圈
        
        for r in range(row):
            for c in range(col):
                if dfs(r, c, 0): # 從word中第一個字開始 # 也只找第一個字
                # 若此指令為true，也就是上面回傳true
                    return True
        return False

---

**:warning: 錯誤語法**
:::warning
換行 : 在一行末尾加上‘\’
從程式碼中清楚的判斷這個輸出是bool還是list還是int等等
:::

**:thumbsup:學習**
:::success
函數中若有return就會跳出該函數，不會執行下面的程式碼
若是return沒有給資料，也會跳回到呼叫該函式的區塊，回傳值的結果是 None

集合不會包含重複的資料
set.add(value)
set.remove(value)
檢查元素是否在集合 : r, c in set
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=pfiQ_PS1g8E
Provided by. NeetCode

###### tags: `graph` `medium` `leetcode`