두 개의 문자열 s와 t가 있다고 가정합니다. s에서 가장 작은 부분 문자열을 찾아야 합니다. 여기서 t는 부분 문자열의 부분 시퀀스이기도 합니다. 해당 유형의 하위 문자열이 존재하지 않는 경우 빈 문자열을 반환하고 가장 작은 하위 문자열이 여러 개 있는 경우 가장 왼쪽에 있는 문자열을 사용합니다.
따라서 입력이 s ="abcbfbghfb", t ="fg"와 같으면 출력은 fbg
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=S
의 크기 -
dp :=무한대로 초기화된 크기 N의 새 목록
-
범위 0에서 N − 1까지의 i에 대해 다음을 수행합니다.
-
S[i]가 T[0]과 같으면
-
dp[i] :=1
-
-
-
범위 1에서 T − 1까지의 j에 대해 다음을 수행합니다.
-
마지막 :=새 지도
-
dp2 :=무한대로 초기화된 크기 N의 새 목록
-
범위 0에서 N까지의 i에 대해 수행
-
S[i]가 T[j]와 같으면
-
prev_i :=마지막에서 T[j − 1]의 값을 반환
-
prev_i가 null이 아니면
-
dp2[i] :=dp[prev_i] + (i − prev_i)
-
-
마지막[S[i]] :=i
-
-
dp :=dp2
-
-
-
m :=dp의 최소값
-
i :=dp에 m을 포함하는 인덱스를 반환
-
m이 무한대이면
-
빈 문자열 반환
-
-
반환 S[인덱스 i − dp[i] + 1에서 i까지]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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")) 입력
"abcbfbghfb","fg"
출력
fbg