1 public class Solution {  2     static final int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};  3       4     public List<String> findWords(char[][] board, String[] words) {  5         Set<String> res = new HashSet<String>();  6         Trie trie = new Trie();  7         boolean[][] visited = new boolean[board.length][board[0].length];  8         for(int i = 0; i < words.length; i++) {  9             trie.insert(words[i]); 10         } 11         for(int i = 0; i < board.length; i++) { 12             for(int j = 0; j < board[0].length; j++) { 13                 dfs(res, board, "", i, j, trie, visited); 14             } 15         } 16         return new ArrayList<String>(res); 17     } 18      19     private void dfs(Set<String> res, char[][] board, String word, int x, int y, Trie trie, boolean[][] visited) { 20         if(x < 0 || y < 0 || x >= board.length || y >= board[0].length || visited[x][y]) { 21             return; 22         } 23         word += board[x][y]; 24         if(!trie.startsWith(word)) { 25             return; 26         } 27         if(trie.search(word)) { 28             res.add(word); 29         } 30         visited[x][y] = true; 31         for(int[] dir: dirs) { 32             dfs(res, board, word, x + dir[0], y + dir[1], trie, visited); 33         } 34         visited[x][y] = false; 35     } 36      37     class TrieNode { 38         char c; 39         boolean isLeaf; 40         TrieNode[] next; 41         // Initialize your data structure here. 42         public TrieNode() { 43             next = new TrieNode[26]; 44             isLeaf = false; 45         } 46     } 47      48     public class Trie { 49         private TrieNode root; 50      51         public Trie() { 52             root = new TrieNode(); 53              54         } 55      56         // Inserts a word into the trie. 57         public void insert(String word) { 58             if(word == null || word.length() == 0) { 59                 return; 60             } 61             TrieNode cur = root; 62             for(int i = 0; i < word.length(); i++) { 63                 char c = word.charAt(i); 64                 int index = c - ‘a‘; 65                 if(cur.next[index] == null) { 66                     cur.next[index] = new TrieNode(); 67                     cur.next[index].c = c; 68                 } 69                 cur = cur.next[index]; 70             } 71             cur.isLeaf = true; 72         } 73      74         // Returns if the word is in the trie. 75         public boolean search(String word) { 76             if(word == null || word.length() == 0) { 77                 return true; 78             } 79             TrieNode cur = root; 80             for(int i = 0; i < word.length(); i++) { 81                 char c = word.charAt(i); 82                 int index = c - ‘a‘; 83                 if(cur.next[index] == null) { 84                     return false; 85                 } 86                 cur = cur.next[index]; 87             } 88             return cur.isLeaf; 89         } 90      91         // Returns if there is any word in the trie 92         // that starts with the given prefix. 93         public boolean startsWith(String prefix) { 94             if(prefix == null || prefix.length() == 0) { 95                 return true; 96             } 97             TrieNode cur = root; 98             for(int i = 0; i < prefix.length(); i++) { 99                 char c = prefix.charAt(i);100                 int index = c - ‘a‘;101                 if(cur.next[index] == null) {102                     return false;103                 }104                 cur = cur.next[index];105             }106             return true;107         }108     }109             110 }