# My Java Solution DFS + Trie 97% what is the solutions in the head !! little one..

• ``````/**
* Trie + DFS
* */
class TrieNode {
boolean isLeaf = false;
TrieNode[] next;
TrieNode(){
next = new TrieNode[26];
}
}

class Trie {
TrieNode root;

Trie() {
root = new TrieNode();
}
/**
* @param word :the word to be inserted
* @param i :the index of the pos of analyse combination
* @param n1 :the point to analyse the construction of the word
* @param count :the most number of the word it can consists of
* */
public boolean search(String word, int i, TrieNode n1, int count) {
if (i == word.length() && count >= 2) {
return true;
}
for (; i < word.length(); i ++) {
int k = word.charAt(i) - 'a';
if (n1.next[k] != null) {
if (n1.next[k].isLeaf) {
if (search(word, i + 1, root, count + 1)) {
return true;
}
}
n1 = n1.next[k];
}else {
if (count == 0) break;
return false;
}
}
return false;

}

public void insert (String word) {
TrieNode p = root;
for (int i = 0 ; i < word.length(); i ++) {
int k = word.charAt(i) - 'a';
if (p.next[k] == null) {
p.next[k] = new TrieNode();
}
p = p.next[k];
}
p.isLeaf = true;
}
}
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});

Trie trie = new Trie();
List<String> res = new ArrayList<>();
for (String str : words) {
if (trie.search(str, 0,trie.root, 0 )){