Chương trình đếm số từ trong danh sách là dãy con của chuỗi cho trước bằng Python

Cho danh sách words và chuỗi s. Đếm số từ trong words là dãy con (subsequence) của s.

Ví dụ: words = ["xz","xw","y"], s="xyz" → 2 ("xz" và "y").

Giải thuật

• Nhóm các từ theo ký tự đầu tiên vào từ điển d.
• Duyệt từng ký tự c trong s:
  • Lấy danh sách từ đang chờ ký tự c.
  • Xóa danh sách chờ tại c.
  • Với mỗi từ: nếu còn 1 ký tự → tăng đếm; ngược lại bỏ ký tự đầu và thêm vào nhóm chờ của ký tự tiếp theo.
• Phức tuyến O(|s| + tổng độ dài words).

Ví dụ minh họa

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