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

তিনটি স্ট্রিং s1, s2, s3 দেওয়া আছে। আমাদের তিনটি স্ট্রিং-এ কমন এমন সবচেয়ে বড় সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে।

উদাহরণস্বরূপ, s1 = "ababchemxde", s2 = "pyakcimde", s3 = "oauctime" হলে আউটপুট ৪, কারণ "acme" সবচেয়ে বড় কমন সাবসিকোয়েন্স।

সমাধানের পদ্ধতি (৩D ডাইনামিক প্রোগ্রামিং)

m, n, o = তিনটি স্ট্রিং-এর দৈর্ঘ্য।
dp = আকার (m+1) x (n+1) x (o+1) এর ৩D অ্যারে, সব ০ দিয়ে ইনিশিয়ালাইজড।
ট্রিপল নেস্টেড লুপ i=1..m, j=1..n, k=1..o:
- যদি s1[i-1] == s2[j-1] == s3[k-1], তবে dp[i][j][k] = 1 + dp[i-1][j-1][k-1]।
- অন্যথায়, dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])।
dp[m][n][o] রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, s1, s2, s3):
        m, n, o = len(s1), len(s2), len(s3)
        dp = [[[0]*(o+1) for _ in range(n+1)] for __ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                for k in range(1, o+1):
                    if s1[i-1] == s2[j-1] == s3[k-1]:
                        dp[i][j][k] = 1 + dp[i-1][j-1][k-1]
                    else:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
        return dp[m][n][o]

ob = Solution()
s1 = "ababchemxde"
s2 = "pyakcimde"
s3 = "oauctime"
print(ob.solve(s1, s2, s3))

ইনপুট

"ababchemxde", "pyakcimde", "oauctime"