212. Word Search II

The basic idea of the problem is saving the words of dictionary into a trie. Unlike 208. Implement Trie (Prefix Tree), we don't need to implement search and beginWith. In order to accelerate the algorithm, we save the word in Trie if current trie is a terminal node (corresponds to a word). The detailed steps are as following:

1. At first, we traverse the words in dictionary to build the trie.
2. Then we dfs each element in board, record any words that appear in trie. In order to remove duplicate elements in the result, the trie that current found word corresponds to will be set as non terminal node.

class Trie {
    Trie array[] = new Trie[26];
    String word = null; // the word current trie corresponds to
}

int array[][] = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<String> findWords(char[][] board, String[] words) {
    List<String> resultList = new ArrayList<String>();
    Trie trie = new Trie();
    for(int i = 0; i < words.length; i++)  // traverse words in dictionary to build a trie
	build(words[i], trie);
    for(int i = 0 ; i < board.length; i++)
	for(int j = 0; j < board[0].length; j++)
	    dfs(board, i, j, resultList, trie);
    return resultList;
}

public void build(String word, Trie trie) {
    char wordArray[] = word.toCharArray();
    for(int i = 0; i < wordArray.length; i++) {
	if( trie.array[wordArray[i] - 'a'] == null )
	    trie.array[wordArray[i] - 'a'] = new Trie();
	trie = trie.array[wordArray[i] - 'a'];
    }
    trie.word = word;
}

public void dfs(char[][] board, int r, int c, List<String> resultList, Trie trie) {
    if( trie.word != null ) {
	resultList.add(trie.word);
	trie.word = null; // remove duplicate element
    }
    if( r >= 0 && c >= 0 && r < board.length && c < board[0].length && 
	    board[r][c] != '1' && trie.array[board[r][c] - 'a'] != null ) {
	char s = board[r][c];
	board[r][c] = '1';
	for(int i = 0; i < array.length; i++)
	    traverse(board, r + array[i][0], c + array[i][1], resultList, trie.array[s - 'a']);
	board[r][c] = s;
    }
}