LeetCode 720 词典中最长单词：HashSet+前缀链，避免 contains 误区

北京这地方，真能把中年人的体面一点点磨掉。

44 岁，财务总监，十多年经验，按理说不算差吧？放在公司里，能管账、能控风险、能扛审计，怎么也不是新人能随便替的。

可一到招聘市场，味儿就变了。求职 时 HR 一看年龄，先沉默两秒，后面什么经验、项目、证书，好像都得打个折。

高管岗少，企业又想要便宜、年轻、能熬的。北京机会多是真的，卷起来也是真的狠。你以为自己在选公司，结果发现公司也在筛年龄，筛行业，筛成本。

她甚至开始想，实在不行就离开北京。一个人在一座城熬了这么多年，最后被迫考虑退场，多少有点难受。

面试题：词典中最长的单词

这题看着像在数组里挑一个最长字符串，手一快就会写成 contains() 判断。

然后就挂。

输入是这样的：

["w","wo","wor","worl","world"]

答案是 world，没问题。

但换成：

["a","banana","app","appl","ap","apply","apple"]

答案不是 banana，而是 apple。

原因很简单，题目要的不是“词典里最长的单词”，而是“能从一个字母开始，每次加一个字母，并且每一步都在词典里出现过”的最长单词。

也就是说，apple 要成立，必须有：

a
ap
app
appl
apple

少一个都不行。

这个条件很容易被写歪。我见过有人直接判断：

word.contains(prefix)

这就离谱了。contains 看的是子串，不是前缀链。还有人每个单词都从头截一遍，然后去数组里找，能过小数据，一上量就开始慢。

我一般会用 HashSet 做。原因不复杂：这题查存在性特别多，别拿 List 硬扫。

关键判断就一句：一个单词能进候选，前提是它去掉最后一个字符之后，已经是一个合法单词。

比如 apple 能不能用，不用从 a 一直查到 appl，只要排序后保证短词在前面，判断 appl 合法就够了。这道题在 LeetCode 上其实就是 720 号“词典中最长的单词”，HashSet 加排序的思路比建 Trie 更直接。

代码可以这么写：

import java.util.*;

public class LongestDictionaryWord {

    public String findLongest(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        Arrays.sort(words, (left, right) -> {
            if (left.length() != right.length()) {
                return left.length() - right.length();
            }
            return left.compareTo(right);
        });

        Set<String> ready = new HashSet<>();
        String answer = "";

        for (String word : words) {
            if (word == null || word.isEmpty()) {
                continue;
            }

            boolean canBuild = word.length() == 1
                    || ready.contains(word.substring(0, word.length() - 1));

            if (!canBuild) {
                continue;
            }

            ready.add(word);

            if (word.length() > answer.length()) {
                answer = word;
            }
        }

        return answer;
    }
}

这段代码里最关键的不是 HashSet，而是排序。

先按长度升序排，保证短词先处理。长度一样的时候按字典序排，这样有两个同长度答案时，先遇到的一定是字典序更小的那个。

所以更新答案时只需要判断：

if (word.length() > answer.length()) {
    answer = word;
}

不用再写一堆：

if (word.length() == answer.length() && word.compareTo(answer) < 0)

不是不能写，是没必要。前面排序已经把这个活干了。

拿刚才那组数据走一遍：

a      -> 合法，加入 ready
ap     -> 前缀 a 在 ready，合法
app    -> 前缀 ap 在 ready，合法
appl   -> 前缀 app 在 ready，合法
apple  -> 前缀 appl 在 ready，合法
apply  -> 前缀 appl 在 ready，合法
banana -> 前缀 banan 不在 ready，丢掉

最后答案还是 apple，因为 apple 和 apply 一样长，但 apple 字典序更小，排序时它先出现。

这里有个小坑：不要在遍历时直接把所有单词都塞进 ready。

像这样就错了：

Set<String> all = new HashSet<>(Arrays.asList(words));

然后对每个单词检查所有前缀。虽然也能做，但你会多扫很多次字符串。

更麻烦的是，有些人写着写着就变成只判断“前缀存在于原数组”，忘了判断“前缀本身也必须能一步步构造出来”。

比如：

["a", "abc", "abcd"]

abcd 不能算合法。因为 ab 不存在，链断了。

如果用上面的 ready 思路，就不会误判。abc 的前缀 ab 不在 ready，所以 abc 进不去。abcd 的前缀 abc 也进不去。

这种题我不太喜欢一上来就 Trie。

Trie 能做，但对这题有点重。你要建节点、标记结尾、DFS，还要控制字典序。写出来没问题，就是代码量多，现场面试或者笔试里更容易手滑。

除非题目后面追问：“词典会频繁新增，频繁查询最长可构造单词”，那 Trie 才更像个长期方案。

普通版本，用排序加 Set 就够了。

复杂度也很干净。排序是 O(n log n)，每个单词只截一次前缀，整体可以看成和字符串总长度相关。空间就是一个 HashSet，存放已经验证通过的单词。

最后可以补个测试：

public static void main(String[] args) {
    LongestDictionaryWord tool = new LongestDictionaryWord();

    String[] words = {
        "a", "banana", "app", "appl", "ap", "apply", "apple"
    };

    System.out.println(tool.findLongest(words)); // apple
}

这题真正要盯住的不是“最长”，而是“每一层都得站得住”。

最长只是结果。

前缀链才是门槛。