accepted Java Trie solution with explanation

• My solution includes two parts:

1. build up a Trie with all the words from the input array.
2. loop through the words and use the Trie to determine if a word is concatenated from the rest of words.

For step 2, the way I archive is to find the count of sub-words recursively.
I check if each subarray starting from index 0 is a word in the trie. if yes, I can make a recursion call to get the count of words for the rest of string.

Notice that the last word in the count method must be a word in the Trie. if it is not a word, we should skip it.

public class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Trie trie = new Trie();
for (String word : words) {
Trie temp = trie;
char[] chars = word.toCharArray();
for(char c : chars) {
int idx = c - 'a';
if(temp.children[idx] == null){
temp.children[idx] = new Trie();
}
temp = temp.children[idx];
}
temp.word = word;
}
//loop trie to fing all concatenatedWord
List<String> result = new ArrayList<>();
for(String word : words) {
if(containsWords(word.toCharArray(), 0, trie) > 1){
}
}
return result;
}

private int containsWords(char[] chars, int idx, Trie trie) {
Trie temp = trie;
for(int i = idx; i < chars.length; i++){
temp = temp.children[chars[i] - 'a'];
if(temp == null){
break;
}
if(temp.word != null){
if(i == chars.length - 1){
return 1;
}else{
int next = containsWords(chars, i+1, trie);
if(next == 0){
continue;
}else{
return 1 + next;
}
}
}
}
return 0;
}

class Trie {
String word;
Trie[] children = new Trie[26];
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.