# Accepted Solution using Trie Tree

• This solution used the Trie Tree to solve the problem. I think time complexity should be like buildTrie(O(n * L * 26)), add/search(O(L*n)), where n refers the number of words and L refers the length of a world.
Please correct me if I am wrong:)

``````class Solution {
// build and implement Trie
class TrieNode{
boolean isLeaf = false;
char c;
TrieNode[] children;
public TrieNode(char c){
this.c = c;
this.children = new TrieNode[26];
}
}
class Trie{
TrieNode root = new TrieNode(' ');
TrieNode p = root;
p = root;
for (char c: s.toCharArray()){
if (p.children[c - 'a'] == null){
p.children[c - 'a'] = new TrieNode(c);
}
p = p.children[c - 'a'];
}
p.isLeaf = true;
}

public boolean search(String s){
TrieNode p = root;
for (char c: s.toCharArray()){
if (p.children[c - 'a'] == null || !p.children[c - 'a'].isLeaf){
return false;
}
p = p.children[c - 'a'];
}
return p.isLeaf;
}
}

//find the longest valid word
public String longestWord(String[] words) {
if (words == null || words.length == 0){
return "";
}

Trie trie = new Trie();
for (String s: words){
}

String maxWord = "";

for (String s: words){
if (trie.search(s)){
if (s.length() > maxWord.length()){
maxWord = s;
} else if (s.length() == maxWord.length() && s.compareTo(maxWord) < 0){
maxWord = s;
}
}
}
return maxWord;
}
}
``````

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