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

词典里找能逐字母长出来的最长词，返回什么

给一个字符串数组 words。要找一个最长的词 w：它去掉末尾若干字母后，每一个前缀都还在 words 里。多个最长的取字典序最小，一个都没有就返回空串。题面例子 words=["w","wo","wor","worl","world"] 返回 "world"；words=["a","banana","app","appl","ap","apply","apple"] 返回 "apple"。

词在不在词典，和能不能拼出来是两码事

把词典塞进哈希集合、看目标词在不在里面，答的却是错的问题。"world" 在词典里，不代表它能逐字母拼出来：只要 "wor" 缺席，就没法从 "wo" 走到 "worl"，"world" 照样拼不出。真正要查的是它每一个前缀 w、wo、wor、worl 都在词典里，缺一步整条链就断了。

一个词合法，就是沿路每个前缀都是词典里的词

把要求说死：w 合法，当且仅当从空串起，一个字母一个字母往后添，每添一步得到的前缀都恰好是词典里的某个词，一步都不能落空。

能存下所有词、又能顺着字母快速查前缀——这个逐前缀往下探的结构就是 Trie 字典树，也就是把有公共前缀的词合并成一棵树、沿树往下每一步添一个字母。把所有词插进去，每个词末字母的节点打上"是词尾"的标记。查 w 时顺它的字母从根往下走，每落到一个节点就看有没有词尾标记，只要有一步没有，这层前缀就不是词典里的词，w 当场判死。

逐词走一遍 Trie，长度和字典序一起挑答案

建完树，拿每个词走一遍：全程每个落脚节点都带词尾标记，才算能构建。通过的词和当前答案 ans 比长短，比 ans 长（len(ans) ＜ len(w)）就换成它；一样长则留字典序小的，即 ans ＞ w 时换成 w。不依赖排序，扫完所有词，ans 就是最长、同长里字典序最小的那个。

拿题面的 apple 那组词沿字典树逐词往下探

先把七个词都插进 Trie，再逐个查。"a" 走一步落到带词尾标记的节点，通过，ans="a"。"banana" 第一步的 "b" 节点没有词尾标记，判死。"app" 走 a、ap、app 三步全带标记，比 "a" 长，ans="app"；"appl" 再多一步也带标记，ans="appl"；"ap" 能过但只有 2 长，不换；"apply" 五步全带标记，长 5，ans="apply"。

最后是 "apple"，五步也全带标记，长度同样是 5。比字典序：前四位 appl 相同，第五位 e ＜ y，"apple" ＜ "apply"，ans ＞ w 成立，答案换成 "apple"。返回 "apple"，长度 5。

为什么是 O(L)，三个边界先想清

设 L 是所有词的总字符数。建 Trie 时每个字母插一次，逐词查询又把每个字母走一遍，两趟都是 O(L)；节点数最多和总字符数同阶，空间也是 O(L)。等长比字典序、词尾标记别漏是两处易踩的坑。全是单字母词时都能构建，答案取里面字典序最小的。没有单字母词打底，谁都拼不出第一步，ans 始终是空串。单字母词去掉末位是空串，空前缀天然合法，永远通过。

Python

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

C++

#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;
    }
};

Java

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;
    }
}