11E
2+ 1526368976
3+ tags : Hash Table , Trie
24
3- 方法1 :
4- 按大小排序 -> 从最大的开始做contains ()的比较 -> 结果再按照字母表顺序 (lexicographically ) sort一下 .
5- 但是Collections .sort ()了两次 , 而且再list .contains (), 比较慢
5+ #### Sort , HashSet
6+ - 先排序 , 排序以后才能逐个看是否partial string已经存在
7+ - 用 set .contains (substring (0 , n - 1 )) 来查看上一步的 substring 是否存在
8+ - 如果找到 , 因为已经按照字母表排序 , 找到的这个肯定是这个长度里面最符合的解答 .
9+ - 然后brutally找下一个更大的 .
10+ - Sort O (n log n ), O (n ) set space
611
7- 方法2 :
8- 先排序 , 以最简单的size ==1 以及set .contains ()找match .
9- 如果找到 , 因为已经按照字母表排序 , 找到的这个肯定是这个长度里面最符合的解答 .
10- 然后brutally找下一个更大的 .
11- 法2比法1好 , 因为只用了一次sort , nLog (n ). 然后其余都是O (1 )的contains .
12- 法1有两个sort (), 然后在list上面contains (), 所以比较耗时 .
12+ #### Trie
13+ - 可以先sort words Array : 1. 长 string 排在前 ; 2. 相等length , 按照dictionary order 排序
14+ - 全部放入Trie . Trie .insert ()
15+ - 针对sorted words array , 从最长的开始找 Trie .startWith .
16+ - 一旦找到 , 就是符合题意的 , 直接return .
17+ - 注意 : startWith 必须每一个node都是 isEnd , 才满足 '逐个字母拼出' 的条件 .
18+ - Time : build Trie O (mn ) + sort :O (nlogn ) => O (nlogn )
19+ - Space : O (mn )
1320
14- 方法3 :
15- 应该可以有一个用Trie的方式做的 , 还没有考虑 .
21+ ####
22+ - 按大小排序 -> 从最大的开始做contains ()的比较 -> 结果再按照字母表顺序 (lexicographically ) sort一下 .
23+ - 但是Collections .sort ()了两次 , 而且再list .contains (), 比较慢
1624
1725
1826```
4553
4654*/
4755
56+ class Solution {
57+ public String longestWord (String [] words ) {
58+ if (words == null || words .length == 0 ) {
59+ return null ;
60+ }
61+ String result = "" ;
62+ Arrays .sort (words );
63+
64+ final Set <String > set = new HashSet <>();
65+ set .add (result );
66+
67+ for (String word : words ) {
68+ if (set .contains (word .substring (0 , word .length () - 1 ))) {
69+ if (word .length () > result .length ()) {
70+ result = word ;
71+ } else {
72+ result = word .compareTo (result ) < 0 ? word : result ;
73+ }
74+ set .add (word );
75+ }
76+ }
77+
78+ return result ;
79+ }
80+ }
81+
82+
83+
84+
4885/*
86+ Same as above
87+ Thoughts:
88+ 1. Sort lexicographically
89+ 2. Any new word.substring(0, length-1) should appear before itself in the sorted list
90+ 3. save the ongoing matched string in set such that it can be used to do set.contains()
91+ 4. maintain a longest result. Go through entire words array.
92+
93+ Note: bacause it's lexicographically sorted, the very first matched word will be the
94+ exact one we want in this length range. The following step becomes: only look for matched
95+ ones in larger length.
96+ */
97+
98+
99+
100+ /**
101+ Trie Solution
102+
103+ */
104+ class Solution {
105+ class TrieNode {
106+ public boolean isEnd ;
107+ public Map <Character , TrieNode > children ;
108+ public TrieNode () {
109+ this .isEnd = false ;
110+ this .children = new HashMap <>();
111+ }
112+ }
113+ TrieNode root ;
114+
115+ public String longestWord (String [] words ) {
116+ if (words == null || words .length == 0 ) {
117+ return null ;
118+ }
119+
120+ // 1. Longer word is in front. 2. if same length, sort by lexicographically(directory order)
121+ Arrays .sort (words , new Comparator <String >() {
122+ public int compare (String s1 , String s2 ) {
123+ if (s1 .length () != s2 .length ()) {
124+ return s1 .length () > s2 .length () ? -1 : 1 ;
125+ }
126+ return s1 .compareTo (s2 );
127+ }
128+ });
129+
130+ root = new TrieNode ();
131+ for (String word : words ) {
132+ insert (word );
133+ }
134+
135+ for (String word : words ) {
136+ if (startsWith (word )) {
137+ return word ;
138+ }
139+ }
140+
141+ return null ;
142+ }
143+
144+ /** Inserts a word into the trie. */
145+ private void insert (String word ) {
146+ if (word == null || word .length () == 0 ) {
147+ return ;
148+ }
149+
150+ TrieNode node = root ;
151+ for (int i = 0 ; i < word .length (); i ++) {
152+ char c = word .charAt (i );
153+ if (!node .children .containsKey (c )) {
154+ node .children .put (c , new TrieNode ());
155+ }
156+ node = node .children .get (c );
157+ if (i == word .length () - 1 ) {
158+ node .isEnd = true ;
159+ }
160+ }
161+ }
162+
163+ // skip the search function
164+
165+ /** Returns if there is any word in the trie that starts with the given prefix. */
166+ private boolean startsWith (String prefix ) {
167+ if (prefix == null || prefix .length () == 0 ) {
168+ return false ;
169+ }
170+ TrieNode node = root ;
171+ for (int i = 0 ; i < prefix .length (); i ++) {
172+ char c = prefix .charAt (i );
173+ if (!node .children .containsKey (c )) {
174+ return false ;
175+ }
176+ node = node .children .get (c );
177+ // IMPORTANT: check if the input prefix is word, if not, fail to find word
178+ if (!node .isEnd ) {
179+ return false ;
180+ }
181+ }
182+ return true ;
183+ }
184+ }
185+
186+
187+
188+ /*
189+ 竟然是 O(nlogn) + O(nm) + O(nlon), 最差, over complicated
49190Thoughts:
501911. Put arrays in to ArrayList, and Collections.sort(..) by the length
511922. Starting from last element && cut off last index && check for exisitance
@@ -99,37 +240,4 @@ private ArrayList<String> matchWords(final ArrayList<String> wordList) {
99240 }
100241}
101242
102- /*
103- Thoughts:
104- 1. Sort lexicographically
105- 2. Any new word.substring(0, length-1) should appear before itself in the sorted list
106- 3. save the ongoing matched string in set such that it can be used to do set.contains()
107- 4. maintain a longest result. Go through entire words array.
108-
109- Note: bacause it's lexicographically sorted, the very first matched word will be the
110- exact one we want in this length range. The following step becomes: only look for matched
111- ones in larger length.
112- */
113- class Solution {
114- public String longestWord (String [] words ) {
115- if (words == null || words .length == 0 ) {
116- return null ;
117- }
118- String result = "" ;
119- Arrays .sort (words );
120-
121- final Set <String > set = new HashSet <>();
122-
123- for (String word : words ) {
124- if (word .length () == 1 || set .contains (word .substring (0 , word .length () - 1 ))) {
125- result = word .length () > result .length () ? word : result ;
126- set .add (word );
127- }
128- }
129-
130- return result ;
131- }
132- }
133-
134-
135243```
0 commit comments