पायथन में कम से कम सुपरसीक्वेंस की लंबाई खोजने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

मी :=s का आकार, n :=t का आकार
तालिका:=आकार की एक तालिका (n + 1) x (m + 1) और 0 से भरें
मेरे लिए 0 से मी की सीमा में, करें
- j के लिए 0 से n की सीमा में, करें
  - अगर मैं 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]
वापसी एम + एन - टेबल [एम, एन]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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"