LeetCode 面试题 17.15. 最长单词

约 6 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 腾讯 拼多多
标签
数组 字符串 哈希表 字典树

题目描述

✅ 面试题 17.15. 最长单词

image-20260928231516240

题意分析

从给定单词数组中找出一个单词，它能够由数组里的其他单词拼接而成，而且长度尽可能大。同长度有多个候选时返回字典序最小者；不存在合格单词时返回空字符串。

拼接必须完整覆盖候选，不能插入、删除或调整片段内部字符。至少需要两个非空片段，同一个较短单词可以重复使用；不能因为数组中存在同名单词，就把一次整词匹配当成有效拼接。

解法：排序 + 单词拆分 DP

核心思路

[!blue]

一个由至少两个非空词拼成的候选，每个组成词都严格短于它。因此先按长度升序处理，当前候选需要的所有较短词都已经出现，可以放在哈希集合中供查询；同长时再按字典序排序，便于按题意比较候选。

对当前词定义 dp[i]：前 i 个字符是否能由字典里的完整单词拼成。空前缀无需任何片段，令 dp[0] = true。枚举最后一段的起点 j，只有 dp[j] 为真且片段 [j, i) 在字典中，才能将它接到可达前缀后，使 dp[i] 为真。

禁止 j == 0 且 i == 全长 的转移，明确排除仅用一个整词的情况。候选是在验证后才登记进字典，但此前也可能已经登记过一个同名单词，所以仍然需要这个限制。对最终状态的其他合法转移，前缀和最后一段都非空，保证至少由两段组成。

每个可拆候选按“更长优先、同长字典序更小”更新答案。不能在找到第一个可拆词时返回，因为按长度升序处理时，后面还可能出现更长的词。无论当前词是否可拆，都要加入字典：它本身是输入提供的一个单词，可作为后面更长候选的组成片段。

解题步骤

  1. 按长度升序、同长字典序升序排序单词，准备空字典和空答案。
  2. 对每个候选创建前缀可达数组，只将空前缀设为可达。
  3. 对每个前缀终点枚举最后切点，跳过不可达前缀以及直接使用整个候选的单段转移。
  4. 剩余片段属于字典时标记该前缀可达，继续计算直到完整词长。
  5. 完整词可达时按长度和字典序更新答案，再把当前词加入字典。
  6. 处理全部候选后返回答案。

代码实现

class Solution {
    // 先按长度升序处理，可以保证集合里都是不长于当前单词的候选词，拆分判断自然转成单词拆分问题。
    public String longestWord(String[] words) {
        Arrays.sort(
                words,
                (a, b) -> {
                    if (a.length() != b.length()) {
                        return Integer.compare(a.length(), b.length());
                    }

                    return a.compareTo(b);
                });

        Set<String> dict = new HashSet<>();
        String best = "";

        for (String word : words) {
            if (wordBreak(word, dict)) {
                if (word.length() > best.length()
                        || (word.length() == best.length() && word.compareTo(best) < 0)) {
                    best = word;
                }
            }

            // 先验证再登记当前词，后续候选可以使用它的完整拼接能力。
            dict.add(word);
        }

        return best;
    }

    private boolean wordBreak(String word, Set<String> dict) {
        if (dict.isEmpty()) {
            return false;
        }

        int n = word.length();
        boolean[] dp = new boolean[n + 1];

        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // 前缀必须可达，同时禁止空前缀直接接整个词，确保至少两段。
                if (!dp[j] || (j == 0 && i == n)) {
                    continue;
                }

                if (dict.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

import "sort"

func longestWord(words []string) string {
    // 先按长度升序处理，可以保证集合里都是不长于当前单词的候选词，拆分判断自然转成单词拆分问题。
    sort.Slice(words, func(i, j int) bool {
        if len(words[i]) != len(words[j]) {
            return len(words[i]) < len(words[j])
        }
        return words[i] < words[j]
    })

    dict := make(map[string]struct{})
    best := ""

    for _, word := range words {
        if canBreak(word, dict) {
            if len(word) > len(best) || (len(word) == len(best) && word < best) {
                best = word
            }
        }
        // 先验证再登记当前词，后续候选可以使用它的完整拼接能力。
        dict[word] = struct{}{}
    }

    return best
}

func canBreak(word string, dict map[string]struct{}) bool {
    if len(dict) == 0 {
        return false
    }

    n := len(word)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            // 前缀必须可达，同时禁止空前缀直接接整个词，确保至少两段。
            if !dp[j] || (j == 0 && i == n) {
                continue
            }
            if _, ok := dict[word[j:i]]; ok {
                dp[i] = true
                break
            }
        }
    }

    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(WL\log(W+1)+WL^3)$，W 为单词数，L 为最大词长。排序比较最坏需要比较线性数量字符；每个词枚举 $O(L^2)$ 个切分片段，截取或计算字符串哈希还需最多 $O(L)$ 字符操作。
  • 空间复杂度：$O(W+L)$，字典保存输入单词的引用，单词拆分状态和临时片段占线性空间。排序会改变输入数组中的单词顺序。

关键点总结

[!green]

  • 组成片段一定短于合格候选，长度排序保证所需字典已准备好。
  • 可达前缀加一个完整字典片段，构成单词拆分的全部转移。
  • 排除完整单段，才能在存在重复单词条目时仍满足至少两段的要求。
  • 判定可拆与选择最佳答案分开处理，最长和同长字典序条件都要保留。

易错点总结

[!yellow]

  • 只依赖“验证后入字典”排除自身，无法阻止之前同名条目造成的一次整词命中。
  • 片段在字典就直接标记可达，却没有检查它前面的前缀，可能跳过无法拼出的中间内容。
  • 找到任意合格候选就返回，漏掉后面更长的结果。
  • 等长时无条件覆盖，会把字典序更小的已有答案替换掉。
  • 只把已经能拆分的词加入字典，会漏掉组成其他词所需的基础短词；不可拆的输入词也可作为片段。
  • 将同一个短词限制为只能用一次，额外增加了题目没有给出的使用次数限制。

相似题目

题目 难度 关联与区别
472. 连接词 困难 连接词判定相同，本题只选其中最长且字典序最小者，原题返回全部合格词。
139. 单词拆分 中等 字典切分可复用，但本题必须至少两个其他非空单词，不能把候选词自身作为单段匹配。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/67168775
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！