Chương trình tìm số lượng dãy con nhỏ nhất của source nối thành target bằng Python

Cho chuỗi source và target. Tìm số lượng dãy con của source nhỏ nhất mà nối lại được target. Không thể thì trả về -1.

Ví dụ: source="xyz", target="xyzyzz" → 3 ("xyz"+"yz"+"z").

Giải thuật

• Duyệt target bằng con trỏ target_idx.
• Mỗi lần: quét toàn bộ source để khớp nhiều ký tự nhất có thể từ vị trí hiện tại của target.
• Nếu không khớp được ký tự nào → trả về -1.
• Đếm số lần quét source.

Ví dụ minh họa

class Solution:
    def solve(self, s, t):
        s_size, t_size = len(s), len(t)
        concat_count = 0
        target_idx = 0
        while target_idx < t_size:
            source_idx = 0
            temp_index = target_idx
            while source_idx < s_size and target_idx < t_size:
                if s[source_idx] == t[target_idx]:
                    target_idx += 1
                source_idx += 1
            if temp_index == target_idx:
                return -1
            concat_count += 1
        return concat_count

ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))

Đầu vào

"xyz", "xyzyzz"

Đầu ra

3