题目
难度：★★☆☆☆
类型：字符串
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。
注意
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
示例
示例 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"。
解答
这里不建议用暴力求解，我们要留意题目中的条件，所有单词都是根据已有单词在末尾添加一个字母组成的，根据这个原理，我们可以设计一个单词集合，用来存储遍历过的所有单词，并判断新单词是否由单词集合中的单词增加字符获得。
class Solution:
def longestWord(self, words) -> str:
words.sort()
save = set()
res = ""
for word in words:
# 如果单词通过集合中的单词扩展而来，或者单词只有一个字母
if word[:-1] in save or word[:-1] == '':
if len(word) > len(res): # 遇到更长的单词
res = word # 更新结果
save.add(word) # 添加到单词表
return res
如有疑问或建议，欢迎评论区留言~
