title: Word Search using depth-first search
body: <p>I am working a word search problem. I correctly implemented dfs search but there is trival error somewhere else.</p>
  
  <p>For the word in this list ["oath","pea","eat","rain"], "oath" and "eat" can be found in the board:</p>
  
  <pre><code>[ 
   ['o','a','a','n'],
   ['e','t','a','e'],
   ['i','h','k','r'],
   ['i','f','l','v']
                    ]
  </code></pre>
  
  <p>I designed a program to search all the words in a given board. Here is my code using dfs:</p>
  
  <pre><code>public class WordSearchII {
  public List&lt;String&gt; findWords(char[][] board, String[] words) {
  
      List&lt;String&gt; res = new ArrayList&lt;String&gt;();
  
      // in order to reinitailize the board every time after 
      //I search each word in the board
      char[][] temp = new char[board.length][board[0].length];
      for (int i=0; i&lt;board.length; i++){
              for(int j=0; j&lt;board[i].length; j++){
                  temp[i][j]=board[i][j];
              }
          }
  
      for (String word : words){
          board=temp; //reintialize the board
          for (int i=0; i&lt;board.length; i++){
              for(int j=0; j&lt;board[i].length; j++){
                  if (find_word(board, word, i, j, 0))// bfs search
                  res.add(word);
              }
          }
      }
      return res;
  }
  
  public boolean find_word(char[][] board, String word, int i, int j, int index){
  
      if (index==word.length()) return true;
  
      if (i&lt;0 || i&gt;=board.length || j&lt;0 || j&gt;=board[i].length) return false;
  
      if (board[i][j]!=word.charAt(index)) return false;
  
      char temp=board[i][j];
  
      board[i][j] = '*';
  
      if (find_word(board, word, i-1, j, index++)||
          find_word(board, word, i+1, j, index++)||
          find_word(board, word, i, j-1, index++)||
          find_word(board, word, i, j+1, index++)) return true;
  
      board[i][j]= temp;
  
      return false;
  
  }
  }
  </code></pre>
  
  <p>For the given example above, my code returned [eat, eat] weirdly.</p>
  
  <p>Since I iterate through the list of words and judge on by one if they can be found in the board. Even though I failed to find 'oath', 'eat' should not be added twice into the result list.</p>