LeetCode 79 單詞搜尋

題目連結：

https://leetcode.cn/problems/word-search/

以下是使用Go語言實作外觀數列問題的代碼：

func exist(board [][]byte, word string) bool {
    // 擷取網格的行數和列數
    rows := len(board)
    cols := len(board[0])

    // 建立一個二維數組用于标記已通路的單元格
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    // 周遊網格中的每個單元格，以檢查是否存在單詞
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == word[0] && backtrack(board, visited, word, i, j, 0) {
                return true
            }
        }
    }

    return false
}

func backtrack(board [][]byte, visited [][]bool, word string, row, col, index int) bool {
    // 檢查索引是否達到單詞長度，如果是則找到了完整的單詞
    if index == len(word) {
        return true
    }

    // 檢查單元格是否越界或已通路過，或者目前字母與單詞不比對
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || visited[row][col] || board[row][col] != word[index] {
        return false
    }

    // 标記目前單元格為已通路
    visited[row][col] = true

    // 在相鄰的四個方向上進行回溯
    found := backtrack(board, visited, word, row-1, col, index+1) ||
        backtrack(board, visited, word, row+1, col, index+1) ||
        backtrack(board, visited, word, row, col-1, index+1) ||
        backtrack(board, visited, word, row, col+1, index+1)

    // 還原目前單元格的通路狀态，以便在其他路徑中繼續使用
    visited[row][col] = false

    return found
}           

執行用時：120 ms, 在所有 Go 送出中擊敗了76.58%的使用者

記憶體消耗：1.9 MB, 在所有 Go 送出中擊敗了84.00%的使用者

通過測試用例：85 / 85

解題思路：

這段代碼使用了回溯算法來解決問題。主要思路是周遊網格中的每個單元格，找到與單詞的第一個字母比對的單元格作為起點，然後在相鄰的四個方向上繼續搜尋比對下一個字母的單元格。如果成功比對整個單詞，則傳回true，否則傳回false。

回溯函數backtrack的參數包括網格board、已通路标記visited、目标單詞word、目前單元格的行索引row、列索引col和目前比對的字母索引index。

在backtrack函數中，首先檢查索引是否達到單詞長度，如果是則找到了完整的單詞，傳回true。

然後，檢查目前單元格是否越界、已通路過、或者目前字母與目标單詞不比對。如果滿足這些條件之一，傳回false。

如果目前單元格是一個合法的候選單元格，将其标記為已通路，并在相鄰的四個方向上遞歸調用backtrack函數，嘗試比對下一個字母。如果任何一個方向上的遞歸調用傳回true，則表示找到了比對的單詞，直接傳回true。

在遞歸調用完成後，将目前單元格的通路狀态還原，以便在其他路徑中繼續使用。

最後，如果在目前單元格及其相鄰單元格中沒有找到比對的單詞，傳回false。

在exist函數中，首先擷取網格的行數和列數，并建立一個二維數組visited來标記已通路的單元格。

然後，周遊網格中的每個單元格，如果目前單元格的字母與目标單詞的第一個字母比對，并且從目前單元格開始的回溯過程傳回true，則表示找到了比對的單詞，直接傳回true。

如果周遊完所有的單元格都沒有找到比對的單詞，則傳回false。

這樣，通過回溯算法，可以在給定的二維字元網格中判斷目标單詞是否存在。

請注意，以上代碼假設輸入的網格是非空的，并且行數和列數都在有效範圍内。在實際應用中，可能需要根據具體要求進行邊界條件的判斷和錯誤處理。

時間複雜度：

在exist函數中，需要周遊網格中的每個單元格，是以周遊的時間複雜度為O(m*n)，其中m是網格的行數，n是網格的列數。

在backtrack函數中，對于每個單元格，需要在相鄰的四個方向上進行遞歸調用。在最壞的情況下，需要周遊所有的單元格，而每個單元格有四個方向可選，是以遞歸調用的次數為4^k，其中k是目标單詞的長度。是以，遞歸調用的時間複雜度為O(4^k)。

綜上所述，算法的總時間複雜度為O(mn4^k)。

空間複雜度：

在exist函數中，建立了一個二維數組visited來标記已通路的單元格，其大小與網格的大小相同，即O(m*n)。

在backtrack函數中，遞歸調用的棧空間取決于目标單詞的長度k，因為在每一步遞歸調用中，需要存儲目前單元格的行索引、列索引和字母索引。是以遞歸調用的空間複雜度為O(k)。

綜上所述，算法的總空間複雜度為O(m*n + k)。

需要注意的是，以上的時間複雜度和空間複雜度分析是基于回溯算法的情況下，其中每個單元格最多隻會被通路一次。如果網格很大且目标單詞很長，回溯算法的性能可能會較低。可以考慮通過優化算法或使用其他資料結構來提高性能，如字典樹（Trie）等。但在給定的限制條件下，回溯算法是一種可行的解決方案。