두 개의 문자열 S와 T가 있다고 가정하고 T는 W의 하위 시퀀스가 되도록 S의 최소 부분 문자열 W를 찾아야 합니다. S에 T의 모든 문자를 포함하는 창이 없으면 빈 문자열을 반환합니다. 이러한 창이 여러 개 있는 경우 시작 인덱스가 가장 왼쪽에 있는 창을 반환해야 합니다.
따라서 입력이 S ="abcdebdde", T ="bde"와 같으면 출력은 "bdde"보다 먼저 발생하므로 "bcde"가 됩니다. "deb"는 창에서 T의 요소가 순서대로 발생해야 하기 때문에 더 작은 창이 아닙니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
tidx :=0, tlen :=T의 크기
-
n :=S
의 크기 -
i :=0, 길이 :=inf, 시작 :=-1
-
나는
-
S[i]가 T[tidx]와 같으면 -
-
(tidx를 1씩 증가)
-
tidx가 tlen과 같으면 -
-
끝 :=나는 + 1
-
(tidx를 1만큼 감소)
-
tidx>=0일 때 −
-
S[i]가 T[tidx]와 같으면 -
-
(tidx를 1만큼 감소)
-
-
(i를 1 감소)
-
-
(i를 1씩 증가)
-
(tidx를 1씩 증가)
-
end - i <길이이면 −
-
길이 :=끝 - i
-
시작 :=나는
-
-
-
-
(i를 1씩 증가)
-
-
시작이 -1과 같지 않으면 -
-
초기화 i :=시작의 경우, i <시작 + 길이, 업데이트(i를 1만큼 증가)일 때 -
를 수행합니다.-
렛 :=렛 + S[i]
-
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string S, string T) {
int tidx = 0;
int tlen = T.size();
int n = S.size();
int i = 0;
int length = INT_MAX;
int start = -1;
string ret;
while (i < n) {
if (S[i] == T[tidx]) {
tidx++;
if (tidx == tlen) {
int end = i + 1;
tidx--;
while (tidx >= 0) {
if (S[i] == T[tidx]) {
tidx--;
}
i--;
}
i++;
tidx++;
if (end - i < length) {
length = end - i;
start = i;
}
}
}
i++;
}
if (start != -1)
for (int i = start; i < start + length; i++)
ret += S[i];
return ret;
}
};
main(){
Solution ob;
cout << (ob.minWindow("abcdebdde", "bde"));
} 입력
"abcdebdde", "bde"
출력
"bcde"