Word Search

 dfs
class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(board.size()==0) return false;
        if(word.length()==0) return true;
       
        int row=board.size(),col=board[0].size();
         vector<vector<bool>>used(row,vector<bool>(col,false));
        
         for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
               if(search(board,word,0,i,j,used))
                return true;
        return false;       
       
       
    }
    bool search(vector<vector<char> > &board, string word, int index,int i,int j, vector<vector<bool>>&used){
        if(index==word.length()) return true;
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||used[i][j]||word[index]!=board[i][j])
            return false;
        used[i][j]=true;   
        bool res=search(board,word,index+1,i-1,j,used)
               ||search(board,word,index+1,i+1,j,used)
               ||search(board,word,index+1,i,j-1,used)
               ||search(board,word,index+1,i,j+1,used);
       
        used[i][j]=false;
        return res;
        //the above two line can be replaced by:
        //if(res) return true;
        //used[i][j]=false;
        //return false;
    }
};


//another flavor
public boolean exist(char[][] board, String word) {
    if(board == null) return false;
    if(word == null || word.length() == 0) return true;
    boolean [][] visited = new boolean[board.length][board[0].length];
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++)
            if(DFS(board, i, j, word, 0, visited)) return true;
    return false;
}
public boolean DFS(char[][] b, int i, int j, String word, int index, boolean[][] v){
    if(v[i][j] || b[i][j] != word.charAt(index)) return false;
    if(index == word.length() - 1) return true;
    v[i][j] = true;
    if(i != 0 && DFS(b, i - 1, j, word, index + 1, v)) return true;                  
    if(i != b.length - 1 && DFS(b, i + 1, j, word, index + 1, v)) return true;
    if(j != 0 && DFS(b, i, j - 1, word, index + 1, v)) return true;
    if(j != b[0].length - 1 && DFS(b, i, j + 1, word, index + 1, v)) return true;
    v[i][j] = false;
    return false;
}