|
| 1 | +packagehard; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +publicclassWordSearchII { |
| 6 | + |
| 7 | +publicList<String>findWords(char[][]board,String[]words) { |
| 8 | +TrieNoderoot =buildTrie(words); |
| 9 | +List<String>result =newArrayList(); |
| 10 | +for(inti =0;i <board.length;i++){ |
| 11 | +for(intj =0;j <board[0].length;j++){ |
| 12 | +dfs(root,board,i,j,result); |
| 13 | + } |
| 14 | + } |
| 15 | +returnresult; |
| 16 | + } |
| 17 | + |
| 18 | +privatevoiddfs(TrieNoderoot,char[][]board,inti,intj,List<String>result){ |
| 19 | +charc =board[i][j]; |
| 20 | + |
| 21 | +if(c =='#' ||root.children[c -'a'] ==null)return; |
| 22 | + |
| 23 | +if(root.children[c -'a'].word !=null){ |
| 24 | +result.add(root.children[c -'a'].word); |
| 25 | +root.children[c -'a'].word =null;//de-duplicate |
| 26 | + } |
| 27 | +board[i][j] ='#';//mark it as visited to avoid cycles |
| 28 | +if(i >0)dfs(root.children[c -'a'],board,i-1,j,result); |
| 29 | +if(j >0)dfs(root.children[c -'a'],board,i,j-1,result); |
| 30 | +if(i+1 <board.length)dfs(root.children[c -'a'],board,i+1,j,result); |
| 31 | +if(j+1 <board[0].length)dfs(root.children[c -'a'],board,i,j+1,result); |
| 32 | + |
| 33 | +board[i][j] =c; |
| 34 | + } |
| 35 | + |
| 36 | +privateTrieNoderoot; |
| 37 | + |
| 38 | +classTrieNode{ |
| 39 | +Stringword; |
| 40 | +TrieNode[]children =newTrieNode[26]; |
| 41 | + } |
| 42 | + |
| 43 | +privateTrieNodebuildTrie(String[]words){ |
| 44 | +TrieNoderoot =newTrieNode(); |
| 45 | +for(Stringword :words){ |
| 46 | +char[]chars =word.toCharArray(); |
| 47 | +TrieNodetemp =root; |
| 48 | +for(charc :chars){ |
| 49 | +if(temp.children[c -'a'] ==null){ |
| 50 | +temp.children[c -'a'] =newTrieNode(); |
| 51 | + } |
| 52 | +temp =temp.children[c -'a']; |
| 53 | + } |
| 54 | +temp.word =word; |
| 55 | + } |
| 56 | +returnroot; |
| 57 | + } |
| 58 | + |
| 59 | +} |