|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | 3 | importjava.util.ArrayList; |
| 4 | +importjava.util.HashSet; |
4 | 5 | importjava.util.List; |
5 | 6 |
|
6 | 7 | publicclass_212 { |
@@ -68,4 +69,43 @@ private TrieNode buildTrie(String[] words) { |
68 | 69 | returnroot; |
69 | 70 | } |
70 | 71 | } |
| 72 | + |
| 73 | +publicstaticclassSolution2 { |
| 74 | +publicList<String>findWords (char[][]board,String[]words) { |
| 75 | + |
| 76 | +List<String>result =newArrayList(); |
| 77 | +HashSet<String>set =newHashSet(); |
| 78 | +for (Stringword :words) { |
| 79 | +for (inti =0;i <board.length;i++) { |
| 80 | +for (intj =0;j <board[0].length;j++) { |
| 81 | +if (board[i][j] ==word.charAt(0) &&search(board,i,j,0,word)) { |
| 82 | +set.add(word); |
| 83 | + } |
| 84 | + } |
| 85 | + } |
| 86 | + } |
| 87 | +result =newArrayList<>(set); |
| 88 | +returnresult; |
| 89 | + } |
| 90 | + |
| 91 | +privatebooleansearch(char[][]board,inti,intj,intcount,Stringword) { |
| 92 | +if (count ==word.length()) { |
| 93 | +returntrue; |
| 94 | + } |
| 95 | + |
| 96 | +if (i <0 ||i >=board.length ||j <0 ||j >=board[0].length ||board[i][j] !=word.charAt(count)) { |
| 97 | +returnfalse; |
| 98 | + } |
| 99 | + |
| 100 | +chartemp =board[i][j]; |
| 101 | +board[i][j] =' '; |
| 102 | + |
| 103 | +booleanfoundWord =search(board,i +1,j,count +1,word) |
| 104 | + ||search(board,i -1,j,count +1,word) |
| 105 | + ||search(board,i,j +1,count +1,word) |
| 106 | + ||search(board,i,j -1,count +1,word); |
| 107 | +board[i][j] =temp; |
| 108 | +returnfoundWord; |
| 109 | + } |
| 110 | + } |
71 | 111 | } |