Chương trình tìm số lượng dãy con có trong danh sách từ trong python

Giả sử chúng ta có một danh sách các từ và một chuỗi s, chúng ta phải tìm số chuỗi trong danh sách các từ là chuỗi con của s.

Vì vậy, nếu đầu vào giống như words =["xz", "xw", "y"] s ="xyz", thì đầu ra sẽ là 2, vì "xz" và "y" là các dãy con của "xyz".

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

• ans:=0
• d:=một bản đồ trống
• đối với mỗi từ trong các từ, hãy thực hiện
  • chèn từ vào cuối d [word [0]]
• đối với mỗi c trong s, thực hiện
  • l:=d [c]
  • d [c]:=một danh sách mới
  • đối với mỗi từ trong l, do
    • nếu kích thước của từ là 1, thì
      • ans:=ans + 1
    • nếu không,
      • chèn chuỗi con của từ [từ chỉ mục 1 đến cuối] vào cuối d [từ [1]]
• trả lại ans

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

Ví dụ

from collections import defaultdict
class Solution:
   def solve(self, words, s):
      ans = 0

      d = defaultdict(list)
      for word in words:
         d[word[0]].append(word)

      for c in s:
         l = d[c]
         d[c] = []

         for word in l:
            if len(word) == 1:
               ans += 1
            else:
               d[word[1]].append(word[1:])
      return ans
ob = Solution()
words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))

Đầu vào

["xz", "xw", "y"], "xyz"

Đầu ra

2