题目描述
给定一个字符串数组 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" 字典序更小。
约束条件:
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 30
- 所有单词仅包含小写英文字母
解题思路
这道题的核心在于验证每个单词的所有前缀是否都存在于给定的集合中。我们可以从两个角度来思考解决方案。
方案一：暴力排序校验
最直观的想法是先对单词列表进行排序，然后逐个检查。为了确保字典序在长度相同时优先被选中，我们先按字典序排序。对于每个单词，我们需要确认它的所有前缀（包括空串）都在原列表中。
这里有个小技巧：我们在处理前先往列表里补一个空字符串 ''，这样第一个字符的单词也能通过前缀校验。遍历过程中，如果发现某个前缀不在列表中，当前单词就不符合条件，直接跳过。
虽然逻辑简单，但由于每次都要遍历前缀并查询列表，时间复杂度较高，在处理大规模数据时效率会明显下降。
class Solution(object):
def longestWord(self, words):
# 补充空字符串作为基础前缀
words += ['']
# 先按字典序排序，保证同长度下取最小字典序
words.sort()
l = []
word words:
i ((word)):
tmp = word[:i]
tmp words:
:
l.append(word)
(l) == :
l.sort(key= x: (x), reverse=)
l[]
