public String longestWord(String[] words) {

Arrays.sort(words);

int N = words.length;

String res = "";

Stack<String> stack = new Stack<>();

for (int i=0; i<N; i++) {

while (!stack.isEmpty() && stack.peek().length() >= words[i].length()) {

stack.pop();

}

String curr = stack.isEmpty() ? "" : stack.peek();

if (curr.length() + 1 == words[i].length() && words[i].startsWith(curr)) {

stack.push(words[i]);

}

if (!stack.isEmpty() && stack.peek().length() > res.length()) {

res = stack.peek();

}

}

return res;

}

/**

public String longestWord2(String[] words) {

Arrays.sort(words);

Set<String> built = new HashSet<String>();

String res = "";

for (String w : words) {

if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {

res = w.length() > res.length() ? w : res;

built.add(w);

}

}

return res;

}

public String longestWord3(String[] words) {

Trie trie = constructTrie(words);

trie.isWord = true;

String[] res = new String[]{""};

dfs(trie, new StringBuilder(), res);

return res[0];

}

private void dfs(Trie trie, StringBuilder sb, String[] res) {

if (trie == null || !trie.isWord) return;

if (sb.length() > res[0].length()) {

res[0] = sb.toString();

}

for (char ch='a'; ch<='z'; ch++) {

Trie child = trie.children[ch-'a'];

if (child == null) continue;

sb.append(ch);

dfs(child, sb, res);

sb.deleteCharAt(sb.length()-1);

}

}

private Trie constructTrie(String[] words) {

Trie trie = new Trie();

for (String word: words) {

trie.add(word);

}

return trie;

}

class Trie {

Trie[] children = new Trie[26];

boolean isWord;

void add(String word) {

add(word.toCharArray(), 0);

}

void add(char[] word, int i) {

if (i == word.length) {

this.isWord = true;

return;

}

int idx = word[i] - 'a';

if (this.children[idx] == null) {

this.children[idx] = new Trie();

}

this.children[idx].add(word, i+1);

}

}