|
6 | 6 | importjava.util.List; |
7 | 7 | importjava.util.Set; |
8 | 8 |
|
9 | | -/** |
10 | | - * 472. Concatenated Words |
11 | | - * |
12 | | - * Given a list of words, please write a program that returns all concatenated words in the given list of words. |
13 | | -
|
14 | | - A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. |
15 | | -
|
16 | | - Example: |
17 | | - Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] |
18 | | -
|
19 | | - Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] |
20 | | -
|
21 | | - Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; |
22 | | - "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; |
23 | | - "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat". |
24 | | - Note: |
25 | | - The number of elements of the given array will not exceed 10,000 |
26 | | - The length sum of elements in the given array will not exceed 600,000. |
27 | | - All the input string will only include lower case letters. |
28 | | - The returned elements order does not matter. |
29 | | -
|
30 | | - */ |
31 | | - |
32 | 9 | publicclass_472 { |
33 | 10 |
|
34 | | -publicstaticclassSolution1 { |
35 | | -privateTrieNoderoot; |
36 | | -privateintmaxWordLen; |
37 | | - |
38 | | -publicList<String>findAllConcatenatedWordsInADict(String[]words) { |
39 | | -ResultTyperesult =buildTrie(words); |
40 | | -root =result.root; |
41 | | -maxWordLen =result.maxWordLen; |
42 | | - |
43 | | -List<String>validConcatenatedWords =newArrayList(); |
44 | | -for (Stringword :words) { |
45 | | -if (word ==null ||word.length() ==0) { |
46 | | -continue; |
47 | | -} |
48 | | -remove(word,root);/** every word is comprised of every word itself, thus this word itself needs to be removed first for checking it*/ |
49 | | -intn =word.length(); |
50 | | -boolean[]dp =newboolean[n +1]; |
51 | | -dp[0] =true; |
52 | | - |
53 | | -for (inti =1;i <=n;i++) { |
54 | | -for (intj =1;j <=i &&j <=maxWordLen;j++) { |
55 | | -if (!dp[i -j]) { |
56 | | -continue; |
57 | | -} |
58 | | - |
59 | | -StringsubWord =word.substring(i -j,i); |
60 | | -if (contains(subWord,root)) { |
61 | | -dp[i] =true; |
62 | | -break; |
63 | | -} |
64 | | -} |
65 | | -} |
66 | | - |
67 | | -if (dp[n]) { |
68 | | -validConcatenatedWords.add(word); |
69 | | -} |
70 | | -undoRemove(word,root); |
71 | | -} |
72 | | -returnvalidConcatenatedWords; |
73 | | -} |
74 | | - |
75 | | -publicResultTypebuildTrie(String[]words) { |
76 | | -ResultTyperesult =newResultType(); |
77 | | - |
78 | | -TrieNoderoot =newTrieNode(); |
79 | | -intmaxWordLen =0; |
80 | | - |
81 | | -for (Stringword :words) { |
82 | | -maxWordLen =Math.max(maxWordLen,word.length()); |
83 | | -char[]chars =word.toCharArray(); |
84 | | -TrieNodenode =root; |
85 | | -for (inti =0;i <chars.length;i++) { |
86 | | -charc =chars[i]; |
87 | | -if (node.children[c -'a'] ==null) { |
88 | | -node.children[c -'a'] =newTrieNode(); |
89 | | -} |
90 | | -node =node.children[c -'a']; |
91 | | -} |
92 | | -node.isWord =true; |
93 | | -} |
94 | | - |
95 | | -result.root =root; |
96 | | -result.maxWordLen =maxWordLen; |
97 | | -returnresult; |
98 | | -} |
99 | | - |
100 | | -publicclassResultType { |
101 | | -intmaxWordLen; |
102 | | -TrieNoderoot; |
103 | | -} |
104 | | - |
105 | | -// Returns true if the word is in the trie. |
106 | | -publicbooleancontains(Stringword,TrieNoderoot) { |
107 | | -TrieNodenode =root; |
108 | | -for (inti =0;i <word.length();i++) { |
109 | | -if (node.children[word.charAt(i) -'a'] ==null) { |
110 | | -returnfalse; |
111 | | -} |
112 | | -node =node.children[word.charAt(i) -'a']; |
113 | | -} |
114 | | -returnnode.isWord; |
115 | | -} |
116 | | - |
117 | | -// mark that word on |
118 | | -publicvoidundoRemove(Stringword,TrieNoderoot) { |
119 | | -TrieNodenode =root; |
120 | | -for (inti =0;i <word.length();i++) { |
121 | | -node =node.children[word.charAt(i) -'a']; |
122 | | -} |
123 | | -node.isWord =true; |
124 | | -} |
125 | | - |
126 | | -// mark that word off, we are not really deleting that word |
127 | | -publicvoidremove(Stringword,TrieNoderoot) { |
128 | | -TrieNodenode =root; |
129 | | -for (inti =0;i <word.length();i++) { |
130 | | -node =node.children[word.charAt(i) -'a']; |
131 | | -} |
132 | | -node.isWord =false; |
133 | | -} |
134 | | - |
135 | | -classTrieNode { |
136 | | -booleanisWord; |
137 | | -TrieNode[]children =newTrieNode[26]; |
138 | | - |
139 | | -publicTrieNode() { |
140 | | -} |
141 | | -} |
142 | | -} |
143 | | - |
144 | | -publicstaticclassSolution2 { |
145 | | -publicList<String>findAllConcatenatedWordsInADict(String[]words) { |
146 | | -List<String>result =newArrayList<>(); |
147 | | -Set<String>preWords =newHashSet<>(); |
148 | | -/**Words could only be formed by other words that are shorter than itself, so we sort them based on their lengths first.*/ |
149 | | -Arrays.sort(words, (s1,s2) ->s1.length() -s2.length()); |
150 | | - |
151 | | -for (inti =0;i <words.length;i++) { |
152 | | -if (canForm(words[i],preWords)) { |
153 | | -result.add(words[i]); |
154 | | -} |
155 | | -preWords.add(words[i]); |
156 | | -} |
157 | | - |
158 | | -returnresult; |
159 | | -} |
160 | | - |
161 | | -booleancanForm(Stringword,Set<String>dict) { |
162 | | -if (dict.isEmpty()) { |
163 | | -returnfalse; |
164 | | -} |
165 | | -boolean[]dp =newboolean[word.length() +1]; |
166 | | -dp[0] =true; |
167 | | -for (inti =1;i <=word.length();i++) { |
168 | | -for (intj =0;j <i;j++) { |
169 | | -if (dp[j] &&dict.contains(word.substring(j,i))) { |
170 | | -dp[i] =true; |
171 | | -break; |
172 | | -} |
173 | | -} |
174 | | -} |
175 | | -returndp[word.length()]; |
176 | | -} |
177 | | -} |
| 11 | +publicstaticclassSolution1 { |
| 12 | +privateTrieNoderoot; |
| 13 | +privateintmaxWordLen; |
| 14 | + |
| 15 | +publicList<String>findAllConcatenatedWordsInADict(String[]words) { |
| 16 | +ResultTyperesult =buildTrie(words); |
| 17 | +root =result.root; |
| 18 | +maxWordLen =result.maxWordLen; |
| 19 | + |
| 20 | +List<String>validConcatenatedWords =newArrayList(); |
| 21 | +for (Stringword :words) { |
| 22 | +if (word ==null ||word.length() ==0) { |
| 23 | +continue; |
| 24 | +} |
| 25 | +remove(word,root);/** every word is comprised of every word itself, thus this word itself needs to be removed first for checking it*/ |
| 26 | +intn =word.length(); |
| 27 | +boolean[]dp =newboolean[n +1]; |
| 28 | +dp[0] =true; |
| 29 | + |
| 30 | +for (inti =1;i <=n;i++) { |
| 31 | +for (intj =1;j <=i &&j <=maxWordLen;j++) { |
| 32 | +if (!dp[i -j]) { |
| 33 | +continue; |
| 34 | +} |
| 35 | + |
| 36 | +StringsubWord =word.substring(i -j,i); |
| 37 | +if (contains(subWord,root)) { |
| 38 | +dp[i] =true; |
| 39 | +break; |
| 40 | +} |
| 41 | +} |
| 42 | +} |
| 43 | + |
| 44 | +if (dp[n]) { |
| 45 | +validConcatenatedWords.add(word); |
| 46 | +} |
| 47 | +undoRemove(word,root); |
| 48 | +} |
| 49 | +returnvalidConcatenatedWords; |
| 50 | +} |
| 51 | + |
| 52 | +publicResultTypebuildTrie(String[]words) { |
| 53 | +ResultTyperesult =newResultType(); |
| 54 | + |
| 55 | +TrieNoderoot =newTrieNode(); |
| 56 | +intmaxWordLen =0; |
| 57 | + |
| 58 | +for (Stringword :words) { |
| 59 | +maxWordLen =Math.max(maxWordLen,word.length()); |
| 60 | +char[]chars =word.toCharArray(); |
| 61 | +TrieNodenode =root; |
| 62 | +for (inti =0;i <chars.length;i++) { |
| 63 | +charc =chars[i]; |
| 64 | +if (node.children[c -'a'] ==null) { |
| 65 | +node.children[c -'a'] =newTrieNode(); |
| 66 | +} |
| 67 | +node =node.children[c -'a']; |
| 68 | +} |
| 69 | +node.isWord =true; |
| 70 | +} |
| 71 | + |
| 72 | +result.root =root; |
| 73 | +result.maxWordLen =maxWordLen; |
| 74 | +returnresult; |
| 75 | +} |
| 76 | + |
| 77 | +publicclassResultType { |
| 78 | +intmaxWordLen; |
| 79 | +TrieNoderoot; |
| 80 | +} |
| 81 | + |
| 82 | +// Returns true if the word is in the trie. |
| 83 | +publicbooleancontains(Stringword,TrieNoderoot) { |
| 84 | +TrieNodenode =root; |
| 85 | +for (inti =0;i <word.length();i++) { |
| 86 | +if (node.children[word.charAt(i) -'a'] ==null) { |
| 87 | +returnfalse; |
| 88 | +} |
| 89 | +node =node.children[word.charAt(i) -'a']; |
| 90 | +} |
| 91 | +returnnode.isWord; |
| 92 | +} |
| 93 | + |
| 94 | +// mark that word on |
| 95 | +publicvoidundoRemove(Stringword,TrieNoderoot) { |
| 96 | +TrieNodenode =root; |
| 97 | +for (inti =0;i <word.length();i++) { |
| 98 | +node =node.children[word.charAt(i) -'a']; |
| 99 | +} |
| 100 | +node.isWord =true; |
| 101 | +} |
| 102 | + |
| 103 | +// mark that word off, we are not really deleting that word |
| 104 | +publicvoidremove(Stringword,TrieNoderoot) { |
| 105 | +TrieNodenode =root; |
| 106 | +for (inti =0;i <word.length();i++) { |
| 107 | +node =node.children[word.charAt(i) -'a']; |
| 108 | +} |
| 109 | +node.isWord =false; |
| 110 | +} |
| 111 | + |
| 112 | +classTrieNode { |
| 113 | +booleanisWord; |
| 114 | +TrieNode[]children =newTrieNode[26]; |
| 115 | + |
| 116 | +publicTrieNode() { |
| 117 | +} |
| 118 | +} |
| 119 | +} |
| 120 | + |
| 121 | +publicstaticclassSolution2 { |
| 122 | +publicList<String>findAllConcatenatedWordsInADict(String[]words) { |
| 123 | +List<String>result =newArrayList<>(); |
| 124 | +Set<String>preWords =newHashSet<>(); |
| 125 | +/**Words could only be formed by other words that are shorter than itself, so we sort them based on their lengths first.*/ |
| 126 | +Arrays.sort(words, (s1,s2) ->s1.length() -s2.length()); |
| 127 | + |
| 128 | +for (inti =0;i <words.length;i++) { |
| 129 | +if (canForm(words[i],preWords)) { |
| 130 | +result.add(words[i]); |
| 131 | +} |
| 132 | +preWords.add(words[i]); |
| 133 | +} |
| 134 | + |
| 135 | +returnresult; |
| 136 | +} |
| 137 | + |
| 138 | +booleancanForm(Stringword,Set<String>dict) { |
| 139 | +if (dict.isEmpty()) { |
| 140 | +returnfalse; |
| 141 | +} |
| 142 | +boolean[]dp =newboolean[word.length() +1]; |
| 143 | +dp[0] =true; |
| 144 | +for (inti =1;i <=word.length();i++) { |
| 145 | +for (intj =0;j <i;j++) { |
| 146 | +if (dp[j] &&dict.contains(word.substring(j,i))) { |
| 147 | +dp[i] =true; |
| 148 | +break; |
| 149 | +} |
| 150 | +} |
| 151 | +} |
| 152 | +returndp[word.length()]; |
| 153 | +} |
| 154 | +} |
178 | 155 | } |