Q720 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].

解题思路：

1. 按照字典序和长度对字符串列表从小到大排序
2. 用集合set存储满足条件的字符串前缀（不包括字符串最后一个字符）
3. 从短到长滚雪球更新最长字符串

Python 实现：

class Solution:
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        words.sort()  # 先按照字典序排序
        words.sort(key = len)  # 再按长度从小到大排序
        #print(words)
        prefix = set() # 前缀集合
        max_string = ""
        for word in words:
            if len(word) == 1:
                prefix.add(word)
                if len(word) > len(max_string): # 相同长度的字符串，返回字典序小的
                    max_string = word 
            else:
                if word[:-1] in prefix:  # 不包括最后一个字符
                    prefix.add(word)
                    if len(word) > len(max_string):
                        max_string = word
        return max_string

strs1 = ["a","banana","app","appl","ap","apply","apple"]
strs2 = ["t","ti","tig","tige","tiger","e","en","eng","engl","engli", \
"englis","english","h","hi","his","hist","histo","histor","history"]
print(Solution().longestWord(strs1))  # "apple"
print(Solution().longestWord(strs2))  # "english"

补充：

该题涉及到字符串列表的排序问题，需要按照字符串长度从小到大排序，同时按照字典序排序。

假设字符串列表

a =  ["a", "banana", "app", "appl", "ap", "apply", "apple", "ba"]

如果调用 a.sort()，则排序规则只是按照字典序排序，排序后的 a 列表结果如下：

['a', 'ap', 'app', 'appl', 'apple', 'apply', 'ba', 'banana']

如果调用 a.sort(key = len) 或 a.sort(key = lambda x : len(x))，则排序规则只是按照字符串长度排序，如果长度相同按照输入字符串的顺序排序，排序后的 a 列表结果如下：

['a', 'ap', 'ba', 'app', 'appl', 'apply', 'apple', 'banana']

这两种情况不能够同时满足。因此，可以先调用 a.sort() 按照字典序排序，再调用 a.sort(key = len) 或 a.sort(key = lambda x : len(x)) 按照字符串长度从小到大排序，就可以满足需要排序的条件。

注：key 只接受一个参数（x），如果接受两个参数会报错。