Giả sử chúng ta đã cho rằng chuỗi "abc" là hợp lệ. Vì vậy, từ bất kỳ chuỗi hợp lệ V, chúng ta có thể chia V thành hai phần X và Y sao cho X + Y giống với V. (X hoặc Y có thể trống.). Khi đó, X + "abc" + Y cũng hợp lệ. Vì vậy, ví dụ S ="abc", thì các ví dụ về chuỗi hợp lệ là:"abc", "aabcbc", "abcabc", "abcabcababcc". Và một số ví dụ về chuỗi không hợp lệ là:"abccba", "ab", "cababc", "bac". Chúng ta phải kiểm tra true nếu và chỉ khi chuỗi S đã cho là hợp lệ.
Vì vậy, nếu đầu vào giống như “abcabcababcc” thì điều đó là hợp lệ, vì vậy đầu ra sẽ là true.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
xác định một ngăn xếp
-
cho tôi trong phạm vi từ 0 đến kích thước của S
-
nếu st trống hoặc S [i] không giống với ‘c’, thì hãy đẩy S [i] vào ngăn xếp
-
nếu không thì
-
chèn c vào st
-
trong khi kích thước của st> =3
-
c:=top of st và bật phần tử trên cùng từ st
-
b:=top of st và bật phần tử trên cùng từ st
-
a:=top of st và bật phần tử trên cùng từ st
-
temp:=ghép nối tạm thời với một
-
temp:=temp nối với b
-
temp:=ghép nối tạm thời với c
-
nếu nhiệt độ là “abc”, thì hãy chuyển sang lần lặp tiếp theo
-
nếu không thì
-
đẩy a, sau đó b, sau đó c vào st và phá vỡ vòng lặp
-
-
-
-
trả về true, khi st trống, nếu không thì trả về false
-
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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"));
} Đầu vào
“abcabcababcc”
Đầu ra
1