문자열 s가 주어지면 k 중복 제거는 문자열 s에서 k개의 인접하고 동일한 문자를 선택하고 삭제된 부분 문자열의 왼쪽과 오른쪽이 함께 연결되도록 하는 제거로 구성됩니다. 우리는 남은 것을 변경할 수 없을 때까지 주어진 문자열 s에서 k개의 중복 제거를 반복적으로 수행합니다. 이러한 모든 중복 제거가 수행된 후 최종 문자열을 찾아야 합니다. 따라서 입력이 s ="deeedbbcccbdaa" 및 k =3과 같으면 출력은 "aa"가 됩니다. 처음에는 "eee"와 "ccc"를 삭제하고 "ddbbbaa"를 얻은 다음 "bbb"를 삭제합니다. , 문자열은 "dddaa"가 되고 "ddd"는 삭제되고 출력은 "aa"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=빈 문자열
- char-int 쌍에 대해 하나의 스택 생성, n :=문자열 크기
- 0~n
- 범위의 i에 대해
- x :=s[i]
- 스택이 비어 있지 않고 스택 맨 위 요소의 정수 =k인 경우 스택에서 맨 위 요소를 삭제합니다.
- i =n이면 중단
- 스택이 비어 있거나 스택 맨 위의 문자가 x가 아니면 스택에 (x, 1) 쌍을 삽입하고 i를 1만큼 증가시킵니다.
- 그렇지 않으면 스택 상단 요소의 정수 부분을 늘리고 i를 1만큼 늘립니다.
- 스택이 비어 있지 않은 동안
- temp :=스택 상단 요소
- temp의 정수 부분이 0이 아닌 동안
- ans :=ans + temp의 문자 부분
- temp의 정수 부분을 1만큼 감소
- 스택에서 최상위 요소 삭제
- as 문자열을 뒤집고 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans = "";
stack < pair<char, int> > st;
int n = s.size();
for(int i = 0; i <= n;){
char x = s[i];
if(!st.empty() && st.top().second == k)st.pop();
if(i == n)break;
if(st.empty() || st.top().first != x){
st.push({x, 1});
i++;
} else {
st.top().second++;
i++;
}
}
while(!st.empty()){
pair <char, int> temp = st.top();
while(temp.second--) ans += temp.first;
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
} 입력
"deeedbbcccbdaa" 3
출력
aa