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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告