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.
class Solution {
public:
bool existSub(int i, int j, vector<vector<char> > &board, string word){
if(word.size() == )
return true;
if(i < || j < || i >= board.size() || j >= board[].size())
return false;
if(board[i][j] != word[])
return false;
string sub_word = word.substr();
char ch = board[i][j];
board[i][j] = '#';
bool ret = existSub(i - , j, board, sub_word) ||
existSub(i + , j, board, sub_word) ||
existSub(i, j - , board, sub_word) ||
existSub(i, j + , board, sub_word);
if (ret)
return true;
board[i][j] = ch;
return false;
}
bool exist(vector<vector<char> > &board, string word) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(word.size() == )
return true;
for(int i = ; i < board.size(); i++)
for(int j = ; j < board[i].size(); j++)
if(board[i][j] == word[])
if(existSub(i, j, board, word))
return true;
return false;
}
};