@@ -85,4 +85,79 @@ public TrieNode(char c) {
8585 }
8686 }
8787 }
88+
89+ public static class Solution2 {
90+ public List <List <String >>suggestedProducts (String []products ,String searchWord ) {
91+ TrieNode root =buildTrie (products );
92+ List <List <String >>result =new ArrayList <>();
93+ for (int i =1 ;i <=searchWord .length ();i ++) {
94+ String searchTerm =searchWord .substring (0 ,i );
95+ TrieNode tmp =root ;
96+ List <String >searchResult =new ArrayList <>();
97+ for (int j =0 ;j <searchTerm .length ();j ++) {
98+ char c =searchTerm .charAt (j );
99+ if (tmp .children [c -'a' ] ==null ) {
100+ break ;
101+ }else {
102+ tmp =tmp .children [c -'a' ];
103+ }
104+ if (j ==searchTerm .length () -1 ) {
105+ searchResult .addAll (findAllWords (tmp ,searchTerm ));
106+ }
107+ }
108+ result .add (searchResult .size () >3 ?searchResult .subList (0 ,3 ) :searchResult );
109+ }
110+ return result ;
111+ }
112+
113+ private List <String >findAllWords (TrieNode trieNode ,String prefix ) {
114+ List <String >result =new ArrayList <>();
115+ if (trieNode .isWord ) {
116+ result .add (prefix );
117+ if (result .size () >3 ) {
118+ return result ;
119+ }
120+ }
121+ for (TrieNode node :trieNode .children ) {
122+ if (node !=null ) {
123+ result .addAll (findAllWords (node ,prefix +node .val ));
124+ if (result .size () >3 ) {
125+ return result ;
126+ }
127+ }
128+ }
129+ return result ;
130+ }
131+
132+ private TrieNode buildTrie (String []words ) {
133+ TrieNode root =new TrieNode (' ' );
134+ for (String word :words ) {
135+ TrieNode tmp =root ;
136+ for (int i =0 ;i <word .length ();i ++) {
137+ char c =word .charAt (i );
138+ if (tmp .children [c -'a' ] ==null ) {
139+ tmp .children [c -'a' ] =new TrieNode (c );
140+ }
141+ tmp =tmp .children [c -'a' ];
142+ if (i ==word .length () -1 ) {
143+ tmp .isWord =true ;
144+ }
145+ }
146+
147+ }
148+ return root ;
149+ }
150+
151+ public class TrieNode {
152+ TrieNode []children ;
153+ char val ;
154+ boolean isWord ;
155+
156+ public TrieNode (char val ) {
157+ this .children =new TrieNode [26 ];
158+ this .val =val ;
159+ this .isWord =false ;
160+ }
161+ }
162+ }
88163}