词典中最长的单词 图解题解

这道题到底在问什么

输入

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

输出

"world"

输入

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

输出

"apple"

先想最直接的笨办法

准备一个集合 S，专门装「已经确认能逐字构建出来」的词，现在它是空的。答案 ans 也先设成空串。接下来从最短的词开始，一个一个判断、一个一个往 S 里收。（动画第 6 步）

最优解：一步一步想明白

1. 3记住这句:「排序让前缀先到，集合判前缀可达」。下面每一帧都在套它。本题演示数据答案是 car。
2. 4先看原始词典：cat、c、car、dog、ca，顺序是乱的。这样扫的时候，可能先碰到 car 却还没确认 ca、c，没法判断它能不能构建。所以第一件事是排序。
3. 5按「长度从短到长、同长度按字典序」排好后变成 c、ca、car、cat、dog。短的排前面，保证了一个关键性质：任何一个词的前缀，长度都更短，一定已经排在它前面、先被处理过。
4. 6准备一个集合 S，专门装「已经确认能逐字构建出来」的词，现在它是空的。答案 ans 也先设成空串。接下来从最短的词开始，一个一个判断、一个一个往 S 里收。
5. 7轮到第 0 个词 "c"，它只有一个字母。长度为 1 的词去掉末位就是空串。
6. 8空前缀天然算在集合里，所以单字母词永远能构建，"c" 直接通过，准备收进集合。
7. 9把 "c" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "c"。
8. 10轮到第 1 个词 "ca"。把末尾的 "a" 去掉，得到前缀 "c"。只要 "c" 已经在集合 S 里，就说明 "ca" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
9. 11去集合里找前缀 "c"，找到了！高亮的就是它。这说明 "ca" 的每一步前缀都在词典里、都能拼出来，所以 "ca" 也能构建。
10. 12把 "ca" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "ca"。
11. 13轮到第 2 个词 "car"。把末尾的 "r" 去掉，得到前缀 "ca"。只要 "ca" 已经在集合 S 里，就说明 "car" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
12. 14去集合里找前缀 "ca"，找到了！高亮的就是它。这说明 "car" 的每一步前缀都在词典里、都能拼出来，所以 "car" 也能构建。
13. 15把 "car" 收进集合 S（绿色），它比当前答案更长，于是答案更新成 "car"。
14. 16轮到第 3 个词 "cat"。把末尾的 "t" 去掉，得到前缀 "ca"。只要 "ca" 已经在集合 S 里，就说明 "cat" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
15. 17去集合里找前缀 "ca"，找到了！高亮的就是它。这说明 "cat" 的每一步前缀都在词典里、都能拼出来，所以 "cat" 也能构建。
16. 18把 "cat" 收进集合 S。它和当前答案 "car" 一样长，但字典序不比 "car" 更小，所以答案保持 "car" 不变。这正是「同长取字典序最小」的体现。
17. 19轮到第 4 个词 "dog"。把末尾的 "g" 去掉，得到前缀 "do"。只要 "do" 已经在集合 S 里，就说明 "dog" 是在一个可构建词的基础上加一个字母得到的，那它也能构建。
18. 20去集合里找前缀 "do"，没有这一行。也就是说 "do" 自己都拼不出来，那建立在它之上的 "dog" 自然也拼不出来。"dog" 标红，判定不可构建。
19. 21"dog" 不可构建，直接跳过，不放进集合，答案也不动。它变灰，表示彻底出局。继续看下一个词。
20. 22扫完一遍。能构建的词是 c、ca、car、cat 四个，dog 因为缺前缀出局。最长的是长度 3 的 car 和 cat 两个，到了「同长取字典序最小」的关键一步。
21. 23car 和 cat 都长 3，比字典序：前两位都是 ca，第三位 r 比 t 小，所以 car 更小。因为我们排序时 car 排在 cat 前面、先被收下当答案，后来的 cat 同长又不更小就没顶替它。最终答案是 car。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.is_end = False

    def insert(self, w: str):
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: str) -> bool:
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return False
            node = node.children[idx]
            if not node.is_end:
                return False
        return True


class Solution:
    def longestWord(self, words: List[str]) -> str:
        trie = Trie()
        for w in words:
            trie.insert(w)
        ans = ""
        for w in words:
            if trie.search(w) and (
                len(ans) < len(w) or (len(ans) == len(w) and ans > w)
            ):
                ans = w
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Trie {
public:
    Trie* children[26] = {nullptr};
    bool isEnd = false;

    void insert(const string& w) {
        Trie* node = this;
        for (char c : w) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new Trie();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool search(const string& w) {
        Trie* node = this;
        for (char c : w) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr || !node->children[idx]->isEnd) {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        Trie trie;
        for (const string& w : words) {
            trie.insert(w);
        }

        string ans = "";
        for (const string& w : words) {
            if (trie.search(w) && (ans.length() < w.length() || (ans.length() == w.length() && w < ans))) {
                ans = w;
            }
        }
        return ans;
    }
};

import java.util.*;
class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd = false;

    public void insert(String w) {
        Trie node = this;
        for (char c : w.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String w) {
        Trie node = this;
        for (char c : w.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null || !node.children[idx].isEnd) {
                return false;
            }
            node = node.children[idx];
        }
        return true;
    }
}

class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        String ans = "";
        for (String w : words) {
            if (trie.search(w)
                && (ans.length() < w.length()
                    || (ans.length() == w.length() && w.compareTo(ans) < 0))) {
                ans = w;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问