Medium

题目描述

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

注意：单词应该是从左到右逐步构建的，每次添加一个字符到前一个单词的末尾。

示例 1:

输入：words = ["w","wo","wor","worl","world"]
输出："world"
解释：单词"world"可以逐步由"w", "wo", "wor", 和 "worl"添加一个字母组成。

示例 2:

输入：words = ["a","banana","app","appl","ap","apply","apple"]
输出："apple"
解释："apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。

约束:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 30
  • words[i] 由小写英文字母组成。

解题思路

这道题需要找到能够通过逐步添加字符构建而成的最长单词。

核心思路：

  1. 一个单词能够被构建，当且仅当它的所有前缀都在词典中存在
  2. 对于长度为 n 的单词，需要检查长度为 1, 2, …, n-1 的前缀是否都在词典中

解法一：哈希表 + 排序

  • 将所有单词存入哈希表，便于 O(1) 查找
  • 按长度降序、字典序升序排序，这样第一个满足条件的就是答案
  • 对每个单词检查其所有前缀是否存在

解法二：字典树（Trie）

  • 构建字典树，每个节点标记是否为完整单词
  • 从根节点开始 DFS，只访问标记为完整单词的节点
  • 在遍历过程中记录最长路径

推荐解法：哈希表方法，代码简洁且效率较高。对于数据规模较小的情况，哈希表的常数时间查找优势明显。

代码实现

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            if (a.length() != b.length()) {
                return a.length() > b.length();
            }
            return a < b;
        });
        
        for (const string& word : words) {
            bool canBuild = true;
            for (int i = 1; i < word.length(); i++) {
                if (wordSet.find(word.substr(0, i)) == wordSet.end()) {
                    canBuild = false;
                    break;
                }
            }
            if (canBuild) {
                return word;
            }
        }
        
        return "";
    }
};

class Solution:
    def longestWord(self, words: List[str]) -> str:
        word_set = set(words)
        
        words.sort(key=lambda x: (-len(x), x))
        
        for word in words:
            can_build = True
            for i in range(1, len(word)):
                if word[:i] not in word_set:
                    can_build = False
                    break
            if can_build:
                return word
        
        return ""

public class Solution {
    public string LongestWord(string[] words) {
        var wordSet = new HashSet<string>(words);
        
        Array.Sort(words, (a, b) => {
            if (a.Length != b.Length) {
                return b.Length.CompareTo(a.Length);
            }
            return a.CompareTo(b);
        });
        
        foreach (string word in words) {
            bool canBuild = true;
            for (int i = 1; i < word.Length; i++) {
                if (!wordSet.Contains(word.Substring(0, i))) {
                    canBuild = false;
                    break;
                }
            }
            if (canBuild) {
                return word;
            }
        }
        
        return "";
    }
}

var longestWord = function(words) {
    const wordSet = new Set(words);
    
    words.sort((a, b) => {
        if (a.length !== b.length) {
            return b.length - a.length;
        }
        return a.localeCompare(b);
    });
    
    for (const word of words) {
        let canBuild = true;
        for (let i = 1; i < word.length; i++) {
            if (!wordSet.has(word.substring(0, i))) {
                canBuild = false;
                break;
            }
        }
        if (canBuild) {
            return word;
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N log N + M)N为单词数量，排序需要O(N log N)，M为所有单词长度之和，检查前缀需要O(M)
空间复杂度O(M)哈希表存储所有单词需要O(M)空间

相关题目