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

สมมติว่าเรามีสตริงสองตัวคือ s และ t เราต้องการหาความยาวของสตริงที่สั้นที่สุดซึ่งมีทั้ง s และ t เป็นซับซีเควส (subsequence)

ตัวอย่าง

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

แนวทางแก้ปัญหา

ปัญหานี้สามารถแก้ได้โดยใช้ Dynamic Programming เพื่อหา Longest Common Subsequence (LCS) ของสองสตริง จากนั้นคำนวณความยาวซูเปอร์ซีเควสสั้นที่สุดจากสูตร:

ความยาว = len(s) + len(t) - LCS(s, t)

1. สร้างตาราง DP ขนาด (m+1) x (n+1) โดยที่ m = len(s), n = len(t)
2. เติมตารางโดยเปรียบเทียบตัวอักษรแต่ละคู่:
   • ถ้าตัวอักษรตรงกัน: dp[i][j] = 1 + dp[i-1][j-1]
   • ถ้าไม่ตรงกัน: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. คำตอบคือ m + n - dp[m][n]

การใช้งาน (Python)

class Solution:
    def solve(self, s, t):
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return m + n - dp[m][n]

# ทดสอบ
ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))  # Output: 7

ความซับซ้อน

• Time Complexity: O(m × n)
• Space Complexity: O(m × n)