Chương trình đếm số từ nối có trong danh sách bằng python

Giả sử chúng ta có một danh sách các chuỗi; chúng ta phải tìm số từ là nối của các từ khác cũng có trong danh sách. Chúng ta có thể sử dụng lại các từ khi nối và nối bất kỳ số lần nào.

Vì vậy, nếu đầu vào giống như words =["hello", "world", "helloworld", "nổi tiếng", "worldfamous", "lập trình"], thì đầu ra sẽ là 2, vì "helloworld" là nối của " xin chào "và" thế giới ". "worldfamous" là từ ghép của "thế giới" và "nổi tiếng".

Để 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
• đối với mỗi từ trong các từ, hãy thực hiện
  • lớp:=trie
  • đối với mỗi w trong từ, hãy thực hiện
    • nếu w không ở trong lớp, thì
      • layer [w]:=một bản đồ mới
    • lớp:=lớp [w]
  • layer ["*"]:=một bộ trống
  • Định nghĩa một hàm dfs (). Điều này sẽ có từ, num_concatenated_words
  • lớp:=trie
  • đối với mỗi chỉ mục i và từ w trong word, hãy thực hiện
    • nếu "*" ở trong lớp, thì
      • nếu dfs (từ [từ chỉ mục i đến cuối], num_concatenated_words + 1) là Đúng, thì
        • trả về True
      • nếu w không ở trong lớp, thì
        • trả về Sai
    • lớp:=lớp [w]
  • nếu "*" nằm trong lớp và num_concatenated_words> =1, thì
    • trả về True
  • trả về Sai
  • Từ phương thức chính, hãy thực hiện như sau:
  • số lượng:=0
  • đối với mỗi từ trong các từ, hãy thực hiện
    • count:=count + dfs (word, 0)
• số lượng trả lại

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 solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
               layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
         layer = trie

         for i, w in enumerate(word):
            if "*" in layer:
               if dfs(word[i:], num_concatenated_words + 1):
                  return True
            if w not in layer:
               return False
            layer = layer[w]

         if "*" in layer and num_concatenated_words >= 1:
            return True
         return False

      count = 0
     for word in words:
      count += dfs(word, 0)
   return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

Đầu vào

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

Đầu ra

2