มีสตริง source และ target หาจำนวน subsequence น้อยที่สุดของ source ที่ต่อกันแล้วได้ target ถ้าไม่ได้คืน -1
เช่น source="xyz", target="xyzyzz" ให้ 3 เพราะ ["xyz","yz","z"]
ขั้นตอนการแก้ปัญหา
- ใช้ two-pointer: วนอ่าน source หาตัวอักษรตรง target
- แต่ละรอบ source หาได้กี่ตัวใน target
- ถ้าหาไม่ได้เลยในรอบหนึ่ง คืน -1
- นับจำนวนรอบที่ใช้
ตัวอย่างโค้ด
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))
อินพุต
"xyz", "xyzyzz"
เอาต์พุต
3
