Word Search [LeetCode]

Problem Description: http://oj.leetcode.com/problems/word-search/

Basic idea: recursively go forward, use char '#' to mark the char visited, so no extra memory is need, don't forget to recover the previous char if the program cannot go forward.

 1 class Solution {
 2 public:
 3     bool existSub(int i, int j, vector<vector<char> > &board, string word){
 4         if(word.size() == 0)
 5             return true;
 6         if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size())
 7             return false;
 9         if(board[i][j] != word[0])
10             return false;
11         
12         string sub_word = word.substr(1);
14         char ch = board[i][j];
15         board[i][j] = '#';
16         bool ret = existSub(i - 1, j,  board, sub_word) || 
17                 existSub(i + 1, j, board, sub_word) || 
18                 existSub(i, j - 1, board, sub_word) || 
19                 existSub(i, j + 1, board, sub_word);            
21         if (ret) 
22             return true;
23             
24         board[i][j] = ch;
25         return false;
26     }
27     
28     bool exist(vector<vector<char> > &board, string word) {
29         // Note: The Solution object is instantiated only once and is reused by each test case.
30         if(word.size() == 0)
31             return true;
32             
33         for(int i = 0; i < board.size(); i++)
34             for(int j = 0; j < board[i].size(); j++) 
35                 if(board[i][j] == word[0])
36                     if(existSub(i, j, board, word))
37                         return true;
38 
39         return false;
40     }
41 };