# Trie Solution with O(len(input string)) lookup time complexity without the need of traversal&ordering

• The idea is to use an array to store the top 3 results for each node so we don't need to traverse all the Nodes in the subtree and sort them to get the top 3 results. Time complexity decreases from O(nC) to O(C) where n is the total number of sentences in the Trie and C is the length of the input string.

``````class TrieNode {
TrieNode[] children;
boolean isWord;
String word;
int cnt;
TrieNode[] t; //use to store top 3 results in the subtrees
public TrieNode() {
children = new TrieNode[128];
isWord  = false;
word = "";
cnt = 0;
t = new TrieNode[3];
}
}

class Trie {
TrieNode root;
String in;

public Trie() {
root = new TrieNode();
in = "";
}

List<String> lookup() {
TrieNode p = root;
for(int i = 0; i < in.length(); i++) {
char c = in.charAt(i);
if(p.children[c] == null) return Collections.emptyList();
p = p.children[c];
}
List<String> result = new ArrayList<>();
for(TrieNode pt : p.t) {
if(pt != null) result.add(pt.word);
}
return result;
}

void insert(String s, int time) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(p.children[c] == null) p.children[c] = new TrieNode();
p = p.children[c];
}
p.isWord = true;
p.word = s;
p.cnt += time;
TrieNode np = root;
for(int i = 0; i < s.length(); i++) { //update max-result array for each ancestor node of the newly inserted node p
setMax(np, p);
char c = s.charAt(i);
np = np.children[c];
}
setMax(np, p);
}

void setMax(TrieNode np, TrieNode p) {
for(int i = 0; i < 3; i++) {
if(np.t[i] == p) {
sortMax(np.t);
return;
}
}

for(int i = 0; i < 3; i++) {
if(np.t[i] == null) {
np.t[i] = p;
sortMax(np.t);
return;
}
}
TrieNode[] tmp = new TrieNode[4];
for(int i = 0; i < 3; i++) tmp[i] = np.t[i];
tmp[3] = p;
sortMax(tmp);
for(int i = 0; i < 3; i++) np.t[i] = tmp[i];
}
void sortMax(TrieNode[] t) {
List<TrieNode> tmp = new ArrayList<>();
for(TrieNode tp : t) {
if(tp != null) tmp.add(tp);
}
Collections.sort(tmp, new Comparator<TrieNode>() {
@Override
public int compare(TrieNode t1, TrieNode t2) {
if(t1.cnt != t2.cnt) return t2.cnt - t1.cnt;
else return t1.word.compareTo(t2.word);
}
});
for(int i = 0; i < tmp.size(); i++) t[i] = tmp.get(i);
for(int i = tmp.size(); i < t.length; i++) t[i] = null;
}
}

public class AutocompleteSystem {
Trie t;
public AutocompleteSystem(String[] sentences, int[] times) {
t = new Trie();
for(int i = 0; i < sentences.length; i++) {
t.insert(sentences[i], times[i]);
}
}

public List<String> input(char c) {
if(c == '#') {
t.insert(t.in, 1);
t.in = "";
return Collections.emptyList();
}
else {
t.in += c;
return t.lookup();
}
}
}
``````

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