Word Search

题目：

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Given board =
[
  "ABCE",
  "SFCS",
  "ADEE"
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

分析：

这是道基础的DFS题目，里面藏有两个陷阱
(1), 因为每个letter只能用一次，所以需要visited矩阵记录走过的情况
(2), 每次DFS之后记得要把visited矩阵还原回去啊

解法：

class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    bool isInBound(vector<vector<char> > board, int i, int j) {
        return !(i >= board.size() || i < 0 || j >= board[0].size() || j < 0);
    } 

    bool wordSearchHelper(vector<vector<char> > &board, 
                            vector<vector<bool> > &visited,
                            string word, 
                            int index, int i, int j) {

        if (index == word.size() ) {
            return true;
        }

        if (!isInBound(board, i, j) || visited[i][j] || board[i][j] != word[index]) {
            return false;
        }

        visited[i][j] = true;
        bool res = wordSearchHelper(board, visited, word, index + 1, i + 1, j) || wordSearchHelper(board, visited, word, index + 1, i - 1, j) || wordSearchHelper(board, visited, word, index + 1, i, j + 1) || wordSearchHelper(board, visited, word, index + 1, i, j - 1);
        visited[i][j] = false;
        return res;

    }

    bool exist(vector<vector<char> > &board, string word) {
        // write your code here
        if (board.size() == 0 || board[0].size() == 0) {
            return false;
        }
        if (word.size() == 0) {
            return true;
        }
        vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(), false ) );
        bool res = false;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0]) {
                    res = wordSearchHelper(board, visited, word, 0, i, j);
                    if (res) {
                        break;
                    }
                }
            }
            if (res) {
                break;
            }
        }
        return res;
    }
};