ন্যূনতম সংখ্যক অনুবর্তন খুঁজে বের করার প্রোগ্রাম যার সংযোজন পাইথনের লক্ষ্যের মতো

ধরুন আমাদের দুটি স্ট্রিং সোর্স এবং টার্গেট আছে, আমাদেরকে সোর্সের ন্যূনতম সংখ্যক অনুগামী সংখ্যা খুঁজে বের করতে হবে যাতে আমরা সেগুলিকে একত্রিত করলে তা লক্ষ্যের মতোই হবে। যদি এমন কোন ফলাফল না থাকে তবে -1 ফেরত দিন।

সুতরাং, যদি ইনপুটটি উৎস ="xyz" লক্ষ্য ="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