문자열 "abc"가 유효하다고 가정합니다. 따라서 유효한 문자열 V에서 X + Y가 V와 같도록 V를 X와 Y의 두 부분으로 나눌 수 있습니다. (X 또는 Y는 비어 있을 수 있습니다.) 그러면 X + "abc" + Y도 유효합니다. 예를 들어 S ="abc"인 경우 유효한 문자열의 예는 "abc", "aabcbc", "abcabc", "abcabcababcc"입니다. 잘못된 문자열의 몇 가지 예는 "abccba", "ab", "cababc", "bac"입니다. 주어진 문자열 S가 유효한 경우에만 true를 확인해야 합니다.
따라서 입력이 "abcabcababcc"와 같으면 유효하므로 출력은 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
스택 정의
-
범위 0에서 S 크기까지의 i에 대해
-
st가 비어 있거나 S[i]가 'c'와 같지 않으면 S[i]를 스택에 푸시합니다.
-
그렇지 않으면
-
c를 st에 삽입
-
st>=3
의 크기-
c :=st의 상단 및 st의 상단 요소 팝
-
b :=st의 상단 및 st의 상단 요소 팝
-
a :=st의 상단 및 st의 상단 요소 팝
-
temp :=temp는 a
와 연결 -
temp :=temp는 b와 연결
-
temp :=temp는 c
와 연결 -
temp가 "abc"이면 다음 반복으로 이동합니다.
-
그렇지 않으면
-
b를 누른 다음 c를 st로 누르고 루프를 끊습니다.
-
-
-
-
st가 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isValid(string S) {
stack <char> st;
for(int i = 0; i < S.size(); i++){
if(st.empty() || S[i] != 'c'){
st.push(S[i]);
}else{
st.push('c');
while(st.size() >= 3){
char c = st.top();
st.pop();
char b = st.top();
st.pop();
char a = st.top();
st.pop();
string temp = "";
temp += a;
temp += b;
temp += c;
if(temp == "abc"){
continue;
}else{
st.push(a);
st.push(b);
st.push(c);
break;
}
}
}
}
return st.empty();
}
};
main(){
Solution ob;
cout << (ob.isValid("abcabcababcc"));
} 입력
“abcabcababcc”
출력
1