Chương trình tìm số lượng tối thiểu của dãy con có nối giống với đích trong python

Giả sử chúng ta có hai chuỗi nguồn và đích, chúng ta phải tìm số lượng chuỗi con của nguồn tối thiểu mà chúng ta có thể tạo thành sao cho nếu chúng ta nối chúng, nó sẽ giống với đích. Nếu không có kết quả như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào giống như source ="xyz" target ="xyzyzz", thì đầu ra sẽ là 3, vì chúng ta có thể ghép các ["xyz" + "yz" + "z"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• s_size:=kích thước của s, t_size:=kích thước của t
• concat_count:=0, target_idx:=0
• while target_idx
• source_idx:=0
• temp_index:=target_idx
• trong khi source_idx
• nếu s [source_idx] giống với t [target_idx] thì
  • target_idx:=target_idx + 1
• source_idx:=source_idx + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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