前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Q720 Longest Word in Dictionary

Q720 Longest Word in Dictionary

作者头像
echobingo
发布2018-08-22 16:31:50
3020
发布2018-08-22 16:31:50
举报
文章被收录于专栏:Bingo的深度学习杂货店

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:
代码语言:javascript
复制
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:
代码语言:javascript
复制
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 实现:
代码语言:javascript
复制
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"
补充:

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

假设字符串列表

代码语言:javascript
复制
a =  ["a", "banana", "app", "appl", "ap", "apply", "apple", "ba"]

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

代码语言:javascript
复制
['a', 'ap', 'app', 'appl', 'apple', 'apply', 'ba', 'banana']

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

代码语言:javascript
复制
['a', 'ap', 'ba', 'app', 'appl', 'apply', 'apple', 'banana']

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

注:key 只接受一个参数(x),如果接受两个参数会报错。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.08.11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Example 1:
  • Example 2:
  • Note:
  • 解题思路:
  • Python 实现:
  • 补充:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档