WordSearch2.java

import java.util.*;

class TrieNode {
 //Hash map of character to trie node
 HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
 //A string to store the possible found words for each node
 String word = null;
 public TrieNode() {}
}
class Solution {
 char[][] _board = null;
 //The list of found words
 ArrayList<String> _result = new ArrayList<String>();

 public List<String> findWords(char[][] board, String[] words) {
   //Step 1). Construct the Trie
   TrieNode root = new TrieNode();
   //Looping over each word in words list
   for (String word : words) {
    //Node is the index on Trie nodes. Which initially points to the root
     TrieNode node = root;
    
     //looping over each letter of the word
     for (Character letter : word.toCharArray()) {
       //Checking if the current node's children contain the current
      //letter being looped over
       if (node.children.containsKey(letter)) {
         //Moving the index to the node that contains the letter
         node = node.children.get(letter);
       }
       //Else, create a new child node for the current node containing
      //the letter
       else {
         TrieNode newNode = new TrieNode();
         node.children.put(letter, newNode);
         //Updating the index to the new node
         node = newNode;
       }
     }
     node.word = word; //Storing words in Trie (Optimization)
   }

   this._board = board;
    
   //Step 2). Backtracking starting for each cell on the board
   for (int row = 0; row < board.length; ++row) {
     for (int col = 0; col < board[row].length; ++col) {
       if (root.children.containsKey(board[row][col])) {
         backtracking(row, col, root);
       }
     }
   }
   return this._result;
 }

 private void backtracking(int row, int col, TrieNode parent) {
   //Current character on the board
   Character letter = this._board[row][col];
   //The node containing the current letter
   TrieNode currNode = parent.children.get(letter);

   //Checking if the node contains a word
   if (currNode.word != null) {
     //Adding the word to the results and removing it from the node
     //to prevent duplication in the results
     this._result.add(currNode.word);
     currNode.word = null;
   }

   //Marking the current letter before the EXPLORATION
   this._board[row][col] = '#';

   //Exploring neighbor cells in around-clock directions: up, right,
  //down, left
   int[] rowOffset = {-1, 0, 1, 0};
   int[] colOffset = {0, 1, 0, -1};
   for (int i = 0; i < 4; ++i) {
     int newRow = row + rowOffset[i];
     int newCol = col + colOffset[i];
     //If Column or Row is out of the boundary, skip
     if (newRow < 0 || newRow >= this._board.length || newCol < 0
         || newCol >= this._board[0].length) {
       continue;
     }
     if (currNode.children.containsKey(this._board[newRow][newCol])) {
       backtracking(newRow, newCol, currNode);
     }
   }

   //End of EXPLORATION, restore the original letter on the board.
   this._board[row][col] = letter;
   //Optimization: incrementally remove the leaf nodes
   if (currNode.children.isEmpty()) {
     parent.children.remove(letter);
   }
 }
}