# 79. Word Search

## 1.問題&#x20;

* 給予一個陣列, 檢查路徑是否存在

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNdIdBWhh9MXxvha64Z%2F-LNdJVmwWAmve62gnx2c%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%883.11.55.png?alt=media\&token=5fed7404-9d26-424e-8b08-a4a2339c7aa8)

## 2.想法&#x20;

* 提問:
* function header, parameter
* test input
* 說明想法&#x20;
  * 路徑問題, 判斷是否有路徑存在時, 可以由一點(row, col)往上下左右擴散
  * base case:&#x20;
    * 如果index == word.length()時回傳true
    * 如果row, col超過範圍, 或是曾經走訪過, 或是當前走到的字母不等於目標, 則回傳false
* 測試計算複雜度

## 3.程式碼

```
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(search(board, visited, word, i, j, 0)) {
            return true;
        }
            }
        }
        
        return false;
    }
private:
    bool search(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int row, int col, int index){
        if (index == word.length()) {
            return true;
        }
        
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || visited[row][col] || board[row][col] != word[index]) {
            return false;
        }
        visited[row][col] = true;
        if(search(board, visited, word, row + 1, col, index + 1)) {
            return true;
        }
        if(search(board, visited, word, row - 1, col, index + 1)) {
            return true;
        }
        if(search(board, visited, word, row, col + 1, index + 1)) {
            return true;
        }
        if(search(board, visited, word, row, col - 1, index + 1)) {
            return true;
        }
        visited[row][col] = false;
        return false;
    }
};
```
