Cho hai chuỗi s và t. Tìm chuỗi con nhỏ nhất trong s mà t là dãy con (subsequence) của chuỗi con đó. Nếu không tồn tại, trả về chuỗi rỗng. Nếu có nhiều chuỗi con nhỏ nhất, lấy cái bên trái nhất.
Ví dụ: s = "abcbfbghfb", t = "fg" -> kết quả "fbg".
Thuật toán dùng động (DP) với mảng dp lưu độ dài nhỏ nhất kết thúc tại mỗi vị trí.
Ví dụ
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"))
Đầu vào
"abcbfbghfb", "fg"
Đầu ra
fbg