79 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.
For example,

Given board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

class Solution {
public:
    bool helper(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int i, int j) {
        int length = word.size();
        if ( length == 0 ) return true;
        int m = board.size();
        int n = board[0].size();
        if ( i <= -1 or i >= m or j <= -1 or j >= n ) return false;
        if ( board[i][j] != word[0] or visited[i][j]) return false;
        visited[i][j] = true;
        if ( helper(board, visited, word.substr(1), i+1, j) ) return true;
        if ( helper(board, visited, word.substr(1), i-1, j) ) return true;
        if ( helper(board, visited, word.substr(1), i, j+1) ) return true;
        if ( helper(board, visited, word.substr(1), i, j-1) ) return true;
        // note this step!
        visited[i][j] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        if ( m == 0 ) return false;
        int n = board[0].size();
        if ( n == 0 ) return false;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for ( int i = 0; i <= m-1; i++ ) {
            for ( int j = 0; j <= n-1; j++ ) {
                if ( helper(board, visited, word, i, j) ) return true;
            }
        }
        return false;
    }
};

Notes
这里注意一个小细节：对于visited是pass by reference还是pass by value. pass by value固然可以，但是会超时。是否可以pass by reference，需要注意一下的是如果在调用help之后返回的是false， 那么visited矩阵中的所有成员必然已经变为false. 所以pass by reference不会出现问题。（仔细体会。。。）