題目

難度：★★☆☆☆
類型：字符串

給出一個字符串數(shù)組words組成的一本英語詞典。從中找出最長的一個單詞，該單詞是由words詞典中其他單詞逐步添加一個字母組成。若其中有多個可行的答案，則返回答案中字典序最小的單詞。

若無答案，則返回空字符串。

注意
所有輸入的字符串都只包含小寫字母。
words數(shù)組長度范圍為[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"。

解答

這里不建議用暴力求解，我們要留意題目中的條件，所有單詞都是根據(jù)已有單詞在末尾添加一個字母組成的，根據(jù)這個原理，我們可以設(shè)計一個單詞集合，用來存儲遍歷過的所有單詞，并判斷新單詞是否由單詞集合中的單詞增加字符獲得。

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                  # 更新結(jié)果
                save.add(word)                  # 添加到單詞表
        return res

如有疑問或建議，歡迎評論區(qū)留言~