পাইথনে সংক্ষিপ্ততম সুপারসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে। আমাদের ক্ষুদ্রতম স্ট্রিংটির দৈর্ঘ্য খুঁজে বের করতে হবে যাতে s এবং t উভয়ই পরবর্তি হিসেবে থাকে।

সুতরাং, যদি ইনপুট s ="pipe" t ="people" এর মত হয়, তাহলে আউটপুট হবে 7, একটি সম্ভাব্য সুপারসিকোয়েন্স হল "pieople"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=s এর আকার, n :=t এর আকার
টেবিল :=আকারের একটি টেবিল (n + 1) x (m + 1) এবং 0 দিয়ে পূরণ করুন
0 থেকে m রেঞ্জের জন্য, করুন
- 0 থেকে n রেঞ্জের মধ্যে j এর জন্য, করুন
  - যদি আমি 0 এর মত হয় বা j 0 এর মত হয়, তাহলে
    - টেবিল[i, j] :=0
  - অন্যথায়,
    - যদি s[i - 1] t[j - 1] এর মত হয়, তাহলে
      - টেবিল[i, j] :=1 + টেবিল[i - 1, j - 1]
    - অন্যথায়,
      - টেবিল[i, j] =সর্বোচ্চ টেবিল[i, j - 1] এবং টেবিল[i - 1, j]
ফিরুন m + n - টেবিল[m, n]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, s, t):
      m = len(s)
      n = len(t)
      table = [[0 for i in range(n + 1)] for j in range(m + 1)]
      for i in range(m + 1):
         for j in range(n + 1):
            if i == 0 or j == 0:
               table[i][j] = 0
            else:
               if s[i - 1] == t[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
            else:
               table[i][j] = max(table[i][j - 1], table[i - 1][j])
      return m + n - table[m][n]
ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))

ইনপুট

"pipe", "people"