โปรแกรมค้นหาจำนวนลำดับขั้นต่ำที่มีการต่อกันเหมือนกับเป้าหมายใน python

สมมติว่าเรามี source และ target สองสตริง เราต้องหาจำนวนลำดับย่อยของซอร์สขั้นต่ำที่เราสามารถสร้างได้ ซึ่งถ้าเราเชื่อมมันเข้าด้วยกัน มันจะเหมือนกับเป้าหมาย หากไม่มีผลลัพธ์ดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือน source ="xyz" target ="xyzyzz" ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเชื่อม ["xyz" + "yz" + "z"]

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

• s_size :=ขนาดของ s, t_size :=ขนาดของ t
• concat_count :=0, target_idx :=0
• ในขณะที่ target_idx
• source_idx :=0
• temp_index :=target_idx
• ในขณะที่ source_idx
• ถ้า s[source_idx] เหมือนกับ t[target_idx] แล้ว
  • target_idx :=target_idx + 1
• source_idx :=source_idx + 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