โปรแกรมหาย่อยสตริงที่สั้นที่สุดซึ่งมีสตริงเฉพาะเป็น subsequence ใน Python

ให้สตริง S และ T ต้องการหาย่อยสตริงสั้นที่สุดใน S ที่ทำให้ T เป็น subsequence ของมัน หากไม่มีให้คืนสตริงว่าง หาหลายค่าให้เลือกตัวซ้ายสุด

ตัวอย่าง: S = "abcbfbghfb", T = "fg" → ผลลัพธ์ "fbg"

อัลกอริธึม (Dynamic Programming)

• สร้างอาร์เรย์ dp ขนาด N (ความยาว S) เริ่มต้นค่า infinity
• สำหรับตัวอักษรแรกของ T: ถ้า S[i] == T[0] ให้ dp[i] = 1
• สำหรับตัวอักษรต่อไปของ T: อัปเดต dp2 โดยค้นหาตำแหน่งก่อนหน้าที่ตรงกับตัวอักษร T[j-1]
• หาค่า dp น้อยที่สุด และคืน substring ตรงช่วงนั้น

การนำไปใช้

class Solution:
    def solve(self, S, T):
        INF = float("inf")
        N = len(S)
        dp = [INF] * N
        for i in range(N):
            if S[i] == T[0]:
                dp[i] = 1
        for j in range(1, len(T)):
            last = {}
            dp2 = [INF] * N
            for i in range(N):
                if S[i] == T[j]:
                    prev_i = last.get(T[j-1], None)
                    if prev_i is not None:
                        dp2[i] = dp[prev_i] + (i - prev_i)
                last[S[i]] = i
            dp = dp2
        m = min(dp)
        i = dp.index(m)
        if m == INF:
            return ""
        return S[i - dp[i] + 1 : i + 1]

ob = Solution()
print(ob.solve("abcbfbghfb", "fg"))  # fbg