पायथन में तीन स्ट्रिंग्स के सबसे लंबे कॉमन सबसीक्वेंस की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास तीन स्ट्रिंग्स s1, s2, और s3 हैं, हमें उनके सबसे लंबे कॉमन सबसीक्वेंस की लंबाई ढूंढनी है।

उदाहरण के लिए, यदि इनपुट s1 = "ababchemxde", s2 = "pyakcimde", s3 = "oauctime" है, तो आउटपुट 4 होगा, क्योंकि सबसे लंबा कॉमन सबसीक्वेंस "acme" है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम 3D डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

• m := s1 का आकार, n := s2 का आकार, o := s3 का आकार
• dp := (o + 1) x (n + 1) x (m + 1) आकार का 3D मैट्रिक्स
• 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 = len(s1)
        n = len(s2)
        o = len(s3)
        dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k 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"

आउटपुट

4