LeetCode Word Search II

 1 public class Solution {
 2     public List<String> findWords(char[][] board, String[] words) {
 3         HashSet<String> res = new HashSet<String>();
 4         if(words == null || words.length == 0 || board == null || board.length == 0 || board[0].length == 0){
 5             return new ArrayList(res);
 6         }
 7         Trie trie = new Trie();
 8         for(int i = 0; i<words.length; i++){
 9             trie.insert(words[i]);
10         }
11         
12         boolean [][] used = new boolean[board.length][board[0].length];
13         for(int i = 0; i<board.length; i++){
14             for(int j = 0; j<board[0].length; j++){
15                 findHelper(board,trie,used,"",i,j,res);
16             }
17         }
18         return new ArrayList(res);
19     }
20     private void findHelper(char[][] board, Trie trie, boolean [][] used, String item, int i, int j, HashSet<String> res){
21         
22         if(i<0 || j<0 || i>= board.length || j>=board[0].length || used[i][j]){
23             return;
24         }
25         
26         item = item+board[i][j];
27         if(!trie.startsWith(item)){
28             return;
29         }
30         if(trie.search(item)){
31             res.add(item);
32         }
33         used[i][j] = true;
34         findHelper(board,trie,used,item,i+1,j,res);
35         findHelper(board,trie,used,item,i-1,j,res);
36         findHelper(board,trie,used,item,i,j+1,res);
37         findHelper(board,trie,used,item,i,j-1,res);
38         used[i][j] = false;
39     }
40 }
41 
42 
43 class TrieNode{
44     String val = "";
45     TrieNode [] nexts;
46     public TrieNode(){
47         nexts = new TrieNode[26];
48     }
49 }
50 class Trie{
51     private TrieNode root;
52     public Trie(){
53         root = new TrieNode();
54     }
55     
56     public void insert(String word){
57         TrieNode p = root;
58         for(char c : word.toCharArray()){
59             if(p.nexts[c-‘a‘] == null){
60                 p.nexts[c-‘a‘] = new TrieNode();
61             }
62             p = p.nexts[c-‘a‘];
63         }
64         p.val = word;
65     }
66     
67     public boolean search(String word){
68         TrieNode p = root;
69         for(char c : word.toCharArray()){
70             if(p.nexts[c-‘a‘] == null){
71                 return false;
72             }
73             p = p.nexts[c-‘a‘];
74         }
75         return p.val.equals(word);
76     }
77     
78     public boolean startsWith(String prefix){
79         TrieNode p = root;
80         for(char c : prefix.toCharArray()){
81             if(p.nexts[c-‘a‘] == null){
82                 return false;
83             }
84             p = p.nexts[c-‘a‘];
85         }
86         return true;
87     }
88 }