Từ dài nhất trong từ điển bằng Python

Giả sử chúng ta có một danh sách các từ đại diện cho một Từ điển tiếng Anh, chúng ta phải tìm từ dài nhất trong danh sách từ đã cho mà có thể được xây dựng một ký tự tại một thời điểm bằng các từ khác trong từ. Nếu có thể có nhiều hơn một câu trả lời, thì hãy trả về từ dài nhất có thứ tự thuật ngữ nhỏ nhất. Nếu không có câu trả lời, hãy trả về chuỗi trống.

Vì vậy, nếu đầu vào là ["h", "he", "hel", "hell", "hello"], thì đầu ra sẽ là "hello"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• trie:=một bản đồ mới
• Xác định một hàm insert (). Điều này sẽ có từ
• bây giờ:=trie
• đối với mỗi c trong word, hãy thực hiện
  • if c not in now -
    • bây giờ [c] ={'#', False}, sau đó
  • bây giờ:=bây giờ [c]
  • bây giờ ['#']:=True
• Xác định một hàm tìm kiếm (). Điều này sẽ có từ
• bây giờ:=trie
• đối với mỗi c trong word, hãy thực hiện
  • nếu '#' bây giờ và không phải bây giờ ['#'] là True, thì
    • trả về false
  • bây giờ:=bây giờ [c]
  • quay lại ngay bây giờ ['#']
• đối với mỗi từ trong các từ, hãy thực hiện
  • chèn cuộc gọi (từ)
• ans:=chuỗi trống
• đối với mỗi từ trong các từ, hãy thực hiện
  • nếu tìm kiếm (từ) và (kích thước của từ> kích thước của ans hoặc (kích thước của từ giống với kích thước của ans và từ
  • ans:=word

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"]))

Đầu vào

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

Đầu ra

hello