[LeetCode]Longest Word in Dictionary
作者是 在线疯狂 发布于 2017年11月5日 在 LeetCode.

题目描述：

LeetCode 720. Longest Word in Dictionary

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

• All the strings in the input will only contain lowercase letters.
• The length of words will be in the range [1, 1000].
• The length of words[i] will be in the range [1, 30].

题目大意：

给定一组词组成的字典，判断其中前缀均可以在字典中找到的最长词，若存在长度相同的情况，则返回字典序最小的词。

解题思路：

排序 + 字典

Python代码：

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        wset = set([''])
        ans = ''
        for word in sorted(words):
            if word[:-1] in wset:
                wset.add(word)
                if len(word) > len(ans):
                    ans = word
        return ans

 

本文链接：https://bookshadow.com/weblog/2017/11/05/leetcode-longest-word-in-dictionary/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。