212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

本题开始做的时候考虑的是word search的情况，用了1个hashmap来存储首字母相同的集合，hashset来存储这个集合，但是最后超时了.

后来看了discussion后发现，本题可以使用字典树+回溯法来做，本题需要注意的是，字典树最开始的结点是不会存放数据的，也就是说，开始他是一个空的结点。代码如下：

 1 public class Solution {
 2     public class TrieNode{
 3         String word;
 4         TrieNode[] next = new TrieNode[26];
 5     }
 6     public List<String> findWords(char[][] board, String[] words) {
 7         List<String> res = new ArrayList<String>();
 8         TrieNode trie = new TrieNode();
 9         for(String s:words){
10             TrieNode t = trie;
11             char[] c = s.toCharArray();
12             int i=0;
13             while(i<c.length){
14                 int index = c[i++]-'a';
15                 if(t.next[index]==null)
16                     t.next[index] = new TrieNode();
17                 t = t.next[index];
18                 if(i==c.length){
19                     t.word = s;
20                 }
21             }
22         }
23         for(int i=0;i<board.length;i++){
24             for(int j=0;j<board[0].length;j++){
25                     helper(board,res,i,j,trie);
26                 }
27             }
28         return res;
29     }
30     public void helper(char[][] board,List<String> res,int row,int col,TrieNode trie){
31         char c = board[row][col];
32         if(c=='#'||trie.next[c-'a']==null) return;
33         trie = trie.next[c-'a'];
34         if(trie.word!=null){
35             res.add(trie.word);
36             trie.word = null;
37         }
38         board[row][col]='#';
39         if(row>0) helper(board,res,row-1,col,trie);
40         if(row<board.length-1) helper(board,res,row+1,col,trie);
41         if(col>0) helper(board,res,row,col-1,trie);
42         if(col<board[0].length-1) helper(board,res,row,col+1,trie);
43         board[row][col] = c;
44     }
45 }

trie可以用来解决给定已知条件是数组，并且需要分类这些数组的时候来做。