[Recursive][BackTracking][DFS] Word Search

1. Example
board =
[

["A B  C  E"],
["S  F  C  S"],
["A D  E  E"]

]

word = "ABCCED", -> return true
word= "SEE"          , -> return true
word ="ABCB"      , -> return false

2. Implementation
Q1: word search ?
A1: blind search form every character [i][j], search direction up, left, down, right
Q1: no repeated?
A1: when proceed search form certain character, we CANNOT go thru the start character again. MARKED it
Q1: Recursive?
A1: start nowhere and dig in through => DFS =>recursive
Q1: use index?
A1: index is like a trie, we can avoid some not wanted word in early stage

// NOTE: string matching if ( item == word) {
// NOTE: item don't have to backtracking since we get a new String every time we call helper()

// NOTE
if ( index == word.length() ) { return true; }

// NOTE

if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] || 

board[i][j] != word.chatAt(index) )

// NOTE

boolean res = helper(board, i+1,j,word, index+1,visited) || helper(board, i-1,j,word, index+1,visited) || helper(board, i,j-1,word, index+1, visited) || helper(board, i, j+1, word, index+1, visited)

// Backtracking, only visited for search from start node 

visited[i][j] = false;

// Time:O(m*n)=O(E+V) whole board, Space:O(m*n) call stack
public boolean exist (char[][] board, String word)
{



       // validate the input
       if (board == null || board.length ==0 || board[0].length == 0)
          return false;
       word.trim();
       // NOTE: string.length()
       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 (   helper(board,i,j, word, new string() )  )
             if (  helper(board,i,j,word,0, visited)  )
                   return true;
            }
       }

     

       return false;


}


//private boolean helper(char[][] board, int i, int j, String word, String item)
private boolean helper(char[][] board, int i, int j, String word, int index, boolean[][] visited)
{




       //item = item + board[i][j];
       
       // base case to stop
       // NOTE: string matching
       //if ( item == word)
// NOTE : use index to check word match
      if ( index == word.length()   )
       {
           return true;
       }







       //if (i < 0 || j < 0 || i > board.length || j > board[0].length )
        //   return false; // out of bound and still no word match
        // NOTE: i+1 = len if i = len -1 
       if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j]  || board[i][j] != word.chatAt(index)   )
           return false; // out of bound and still no word match




        visited[i][j] = true
       // recursive call to recursive
       // NOTE: move to top if equal, save the below checking effort
       //item = item + board[i][j];
       //if (helper(board, i+1, j, word, new String(item))
       //    || helper(board, i-1, j, word, new string(item))
       //    || helper(board, i, j+1, word , new String(item))
       //    || helper(board, i, j-1, word , new String(item))
       //   )
       //      return true;
       // NOTE: we need to return false, for nested for loop to go on
      
       boolean res = helper(board, i+1,j,word, index+1,visited)
           || helper(board, i-1,j,word, index+1,visited)
           || helper(board, i,j-1,word, index+1, visited)
           || helper(board, i, j+1, word, index+1, visited);

       // Backtracking, only visited for search from start node
       visited[i][j] = false;
       // NOTE: item don't have to backtracking since we get a new String everytime we call helper()






       return res;



}

3. Similar ones
 (H) Word Search II    
        Word Break II