โปรแกรมค้นหาความยาวของ supersequence ที่สั้นที่สุดใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องหาความยาวของสตริงที่สั้นที่สุดที่มีทั้ง s และ t เป็นตัวรอง

ดังนั้น หากอินพุตเป็นเหมือน s ="pipe" t ="people" ผลลัพธ์จะเป็น 7 เนื่องจากมีความเป็นไปได้ที่จะเกิดลำดับเหนือกว่า "pieople"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

m :=ขนาดของ s, n :=ขนาดของ t
table :=ตารางขนาด (n + 1) x (m + 1) และเติมด้วย 0
สำหรับฉันในช่วง 0 ถึง m ทำ
- สำหรับ j ในช่วง 0 ถึง n ทำ
  - ถ้าฉันเหมือนกับ 0 หรือ j เหมือนกับ 0 แล้ว
    - ตาราง[i, j] :=0
  - มิฉะนั้น
    - ถ้า s[i - 1] เหมือนกับ t[j - 1] แล้ว
      - table[i, j] :=1 + table[i - 1, j - 1]
    - มิฉะนั้น
      - table[i, j] =สูงสุดของ 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 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"