Python字典中最长的单词

假设我们有一个单词列表，表示一个英语字典，我们需要找到给定单词列表中最长的单词，该单词可以通过单词列表中的其他单词逐个字符构建。如果有多个可能的答案，则返回字典序最小的最长单词。如果没有答案，则返回空字符串。

因此，如果输入类似于 ["h","he","hel","hell", "hello"]，则输出将为 "hello"

为了解决这个问题，我们将遵循以下步骤：

  • trie := 一个新的映射
  • 定义一个函数 insert()。这将接收单词
  • now := trie
  • 对于单词中的每个字符 c，执行以下操作：
    • 如果 c 不在 now 中：
      • now[c] = {'#', False}，则
    • now := now[c]
    • now['#'] := True
  • 定义一个函数 search()。这将接收单词
  • now := trie
  • 对于单词中的每个字符 c，执行以下操作：
    • 如果 '#' 在 now 中且 now['#'] 不为 True，则
      • 返回 false
    • now := now[c]
    • 返回 now['#']
  • 对于 words 中的每个单词，执行以下操作：
    • 调用 insert(word)
  • ans := 空字符串
  • 对于 words 中的每个单词，执行以下操作：
    • 如果 search(word) 且（单词的大小 > ans 的大小 或 （单词的大小与 ans 的大小相同且 word < ans）），则
      • ans := word
  • 返回 ans

让我们看看下面的实现，以便更好地理解：

示例

 实时演示

class Solution:
   def longestWord(self, words):
      self.trie = {}
   def insert(word):
      now = self.trie
      for c in word:
         if c not in now: now[c] = {'#': False}
            now = now[c]
         now['#'] = True
   def search(word):
      now = self.trie
      for c in word:
         if '#' in now and not now['#']: return False
            now = now[c]
         return now['#']
         for word in words:
            insert(word)
         ans = ""
         for word in words:
            if (search(word) and (len(word) > len(ans) or (len(word) == len(ans) and word    < ans))):
         ans = word
      return ans
ob = Solution()
print(ob.longestWord(["h","he","hel","hell", "hello"]))

输入

["h","he","hel","hell", "hello"]

输出

hello

更新于: 2020年7月4日

398 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告