पायथन में सबसे छोटे सुपरसीक्वेंस की लंबाई ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं। हमें सबसे छोटी स्ट्रिंग की लंबाई ज्ञात करनी है जिसमें s और t दोनों सबसीक्वेंस के रूप में मौजूद हों।

उदाहरण के लिए, यदि इनपुट है s = "pipe" और t = "people", तो आउटपुट 7 होगा, क्योंकि एक संभावित सुपरसीक्वेंस "pieople" है।

एल्गोरिदम

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• m := s का आकार, n := t का आकार
• table := (n+1) x (m+1) आकार की एक टेबल जिसे 0 से भरा गया हो
• 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])
• return 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
                elif 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"

आउटपुट

7