পাইথনে শর্টেস্ট সুপারসিকোয়েন্সের দৈর্ঘ্য বের করার প্রোগ্রাম

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

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

সমাধানের পদ্ধতি

এই সমস্যা সমাধানের জন্য নিচের ধাপগুলো অনুসরণ করা হবে:

m := s-র আকার, n := t-র আকার
table := (n + 1) x (m + 1) আকারের একটি টেবিল তৈরি করে ০ দিয়ে পূরণ করুন
i = 0 থেকে m পর্যন্ত লুপ চালান:
- j = 0 থেকে n পর্যন্ত লুপ চালান:
  - যদি i == 0 বা j == 0 হয়, তবে table[i][j] := 0
  - অন্যথায়, যদি s[i-1] == t[j-1] হয়, তবে table[i][j] := 1 + table[i-1][j-1]
  - অন্যথায়, table[i][j] := max(table[i][j-1], table[i-1][j])
ফলাফল রিটার্ন করুন: m + n - table[m][n]

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝতে:

class Solution:
    def solve(self, s, t):
        m = len(s)
        n = len(t)
        table = [[0 for _ in range(n + 1)] for _ 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"