# 0079. Word Search
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/word-search/
## 思路
### 第一遍笔记
我先想到的是用DFS的方法，debug超级久。
一开始还忘了走过的点不能走的条件。（其实只需要用一个visited vector来记录走过了哪些点就可以了）
### 第二遍笔记
backtracking
不能用iterative的方法是因为，走过的路不能再走了，所以每次都需要mark起来，往上一层就要un-mark一下
而且也不能用visited，因为一个点visited了的时候可能这个单词就剩下三位，但是也许当这个单词剩下五位的时候，再访问这个点就找到这个单词了
## Code
Java

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(board[i][j]==word.charAt(0)){
                    if(backtrack(board, i, j, word, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean backtrack(char[][] board, int i, int j, String word, int idx){
        int m = board.length;
        int n = board[0].length;
        if(idx == word.length()-1){
            return true;
        }
        board[i][j] = '#';
        if(i-1>=0 && board[i-1][j]==word.charAt(idx+1) && backtrack(board, i-1, j, word, idx+1)) return true;
        if(i+1<m && board[i+1][j]==word.charAt(idx+1) && backtrack(board, i+1, j, word, idx+1)) return true;
        if(j-1>=0 && board[i][j-1]==word.charAt(idx+1) && backtrack(board, i, j-1, word, idx+1)) return true;
        if(j+1<n && board[i][j+1]==word.charAt(idx+1) && backtrack(board, i, j+1, word, idx+1)) return true;
        board[i][j] = word.charAt(idx);
        return false;
    }
}

C++

class Solution {
public:
    int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    bool from_start_exist(vector<vector<char>>& board, vector<vector<int>>& visited, string word, int i, int j, int pos){
        visited[i][j] = true;
        if(pos == word.size()-1){
            return true;
        }
        for(int k = 0;k < 4;k++){
            if(k == 0 && i == board.size()-1){
                continue;
            }
            if(k == 1 && i == 0){
                continue;
            }
            if(k == 2 && j == board[0].size()-1){
                continue;           
            }
            if(k == 3 && j == 0){
                continue;
            }
            int new_i = i+direction[k][0];
            int new_j = j+direction[k][1];
            if(board[new_i][new_j] == word[pos+1]&&visited[new_i][new_j] != true){
                if(from_start_exist(board, visited, word, new_i, new_j, pos+1)){
                    return true;
                }

            }
        }
        visited[i][j] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<int>> visited(board.size(), vector<int>(board[0].size()));
        for(int i = 0;i < board.size();i++){
            for(int j = 0;j < board[0].size();j++){
                if(board[i][j] == word[0]){
                    if(from_start_exist(board, visited, word, i, j, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

## Result
Runtime: 184 ms, faster than **49.46%** of C++ online submissions for Word Search.
Memory Usage: 7.2 MB, less than **97.36%** of C++ online submissions for Word Search.