难度: 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 <= 10001 <= words[i].length <= 30words[i] 都只包含小写字母。运行时间: 31 ms
内存: 16.3 MB
from typing import List
class Solution:
def longestWord(self, words: List[str]) -> str:
# 将单词列表按字典序排序
words.sort()
# 创建一个集合用于快速查找已构建的单词
built_words = set()
# 初始化最长单词为空字符串
longest_word = ""
for word in words:
# 如果当前单词只有一个字母或者它的前缀已经在集合中，说明可以通过逐步添加一个字母构建
if len(word) == 1 or word[:-1] in built_words:
# 将当前单词添加到集合中
built_words.add(word)
# 更新最长单词
if len(word) > len(longest_word):
longest_word = word
return longest_word
该题解的思路是先将单词列表按字典序排序，然后创建一个集合用于快速查找已构建的单词。接着遍历排序后的单词列表，对于每个单词，如果它只有一个字母或者它的前缀已经在集合中，说明可以通过逐步添加一个字母构建，就将当前单词添加到集合中，并更新最长单词。最后返回找到的最长单词。
时间复杂度: O(n log n + n * m)
空间复杂度: O(n)
from typing import List
class Solution:
def longestWord(self, words: List[str]) -> str:
# 将单词列表按字典序排序
words.sort()
# 创建一个集合用于快速查找已构建的单词
built_words = set()
# 初始化最长单词为空字符串
longest_word = ""
for word in words:
# 如果当前单词只有一个字母或者它的前缀已经在集合中，说明可以通过逐步添加一个字母构建
if len(word) == 1 or word[:-1] in built_words:
# 将当前单词添加到集合中
built_words.add(word)
# 更新最长单词
if len(word) > len(longest_word):
longest_word = word
return longest_word
单词列表按字典序排序是为了确保在处理任何单词之前，它的所有可能的前缀已经被处理并存入集合中。这样，在遍历单词时，可以直接检查一个单词的所有前缀是否已构建，从而判断该单词是否可以通过前缀加一个字母的方式构建。这个排序步骤对算法的正确性是至关重要的，因为它保证了单词的逐步构建过程。从效率上讲，排序操作的时间复杂度为O(n log n)，这对整体算法性能有一定影响，但是它是实现算法正确性的必要步骤。
由于单词列表是按字典序排序的，当处理到任何一个单词时，所有较短的单词（包括它的所有前缀）已经在之前被处理过并加入到集合中了。因此，在遍历单词时，如果一个单词的前缀缺失，则说明这个单词无法通过逐步添加一个字母的方式构建。这种排序保证了在添加每个单词之前，它的所有前缀都已经存在于集合中，从而确保了集合的完整性。
如果输入的单词列表中包含重复的单词，由于集合的性质是只保存唯一的项，重复的单词在加入集合时不会产生任何影响。这意味着算法只会处理每个单词一次，重复的单词在逻辑上被忽略。因此，重复的单词不会影响算法找到最长单词的能力，也不会影响最终的输出结果。
在单词长度极其不均匀的情况下，该算法仍然能有效地工作，因为算法主要依赖于单词的前缀是否可以构建出来。即使存在一些极长的单词，只要它们的所有前缀都能逐个构建出来，这些单词就会被考虑在内。性能上，算法的主要瓶颈在于排序（O(n log n)）和遍历单词列表（O(n)），其中n是单词的数量。因此，算法的总体性能主要受输入单词数量的影响，而单词长度的不均匀性对性能的影响相对较小。