โปรแกรมค้นหาจำนวน subsequence ที่มีอยู่ในรายการคำใน python

สมมติว่าเรามีรายการคำและสตริง s เราต้องหาจำนวนสตริงในรายการคำที่เป็นผลสืบเนื่องมาจาก s

ดังนั้น หากอินพุตเป็นเหมือนคำ =["xz", "xw", "y"] s ="xyz" ผลลัพธ์จะเป็น 2 เนื่องจาก "xz" และ "y" เป็นผลสืบเนื่องมาจาก "xyz"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=0
• d :=แผนที่ว่างเปล่า
• สำหรับแต่ละคำในคำ ทำ
  • ใส่คำที่ท้าย d[word[0]]
• สำหรับแต่ละ c ใน s ทำ
  • l :=d[c]
  • d[c] :=รายการใหม่
  • สำหรับแต่ละคำใน l do
    • ถ้า word มีขนาด 1 แล้ว
      • อัน :=ans + 1
    • มิฉะนั้น
      • แทรกสตริงย่อยของ word[จากดัชนี 1 ถึงปลาย] ที่ส่วนท้ายของ d[word[1]]
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

2