题目地址：

https://www.lintcode.com/problem/longest-word-in-dictionary/description

给定一个字符串数组$A$，字符串由小写字母组成。求$A$中最长的字符串$s$，使得$s[0],s[0:1],s[0:2],...,s[0:l_s-2],s$都属于$A$。如果有多个字符串满足条件，则返回字典序最小的那个。

思路是用Trie。先将所有字符串加入Trie，然后从树根开始做DFS（注意这里DFS的时候，搜索字母的顺序一定要按照从$a$到$z$进行，这样就能保证首先搜的字符串是字典序小的），如果一路上节点都被标记为单词，并且得到了长度更长的字符串，就更新答案。代码如下：

public class Solution { class Trie { class Node { boolean isWord; Node[] nexts; public Node() { nexts = new Node[26]; } } private Node root; public Trie() { root = new Node(); } public void insert(String s) { Node cur = root; for (int i = 0; i < s.length(); i++) { int idx = s.charAt(i) - 'a'; if (cur.nexts[idx] == null) { cur.nexts[idx] = new Node(); } cur = cur.nexts[idx]; } cur.isWord = true; } private String res; public void dfs(Node cur, StringBuilder sb) { // 如果遇到没被标记为单词的节点，则直接返回 if (cur != root && !cur.isWord) { return; } // 从'a'到'z'的顺序搜索每个树杈 for (int i = 0; i < cur.nexts.length; i++) { if (cur.nexts[i] != null) { sb.append((char) ('a' + i)); dfs(cur.nexts[i], sb); // 递归返回要回溯 sb.setLength(sb.length() - 1); } } // 如果遇到了更长的单词，就更新res if (cur.isWord && (res == null || sb.length() > res.length())) { res = sb.toString(); } } } /** * @param words: a list of strings * @return: the longest word in words that can be built one character at a time by other words in words */ public String longestWord(String[] words) { // Write your code here Trie trie = new Trie(); for (String word : words) { trie.insert(word); } trie.dfs(trie.root, new StringBuilder()); return trie.res; } }

时空复杂度与具体列表包含哪些单词有关，但通常情况下会比整个列表的字母总数要低很多。