Kiểm tra chuỗi hợp lệ sau thay thế (Check If Word Is Valid After Substitutions) trong C++

Cho chuỗi "abc" là hợp lệ. Từ chuỗi hợp lệ V, chia V thành X và Y (có thể rỗng) sao cho X+Y = V. Khi đó X + "abc" + Y cũng hợp lệ. Ví dụ hợp lệ: "abc", "aabcbc", "abcabc", "abcabcababcc". Không hợp lệ: "abccba", "ab", "cababc", "bac". Kiểm tra chuỗi S có hợp lệ không.

Ví dụ: "abcabcababcc" -> true.

Giải pháp dùng stack:

• Duyệt S, nếu stack rỗng hoặc ký tự không phải 'c' -> push.

• Gặp 'c': push 'c', sau đó while stack.size >= 3: pop c,b,a; nếu "abc" thì tiếp tục, ngược lại push lại a,b,c và break.

• Cuối cùng stack rỗng -> true, ngược lại false.

Ví dụ hoàn chỉnh

#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();
    }
};
int main() {
    Solution ob;
    cout << (ob.isValid("abcabcababcc"));
}

Input

"abcabcababcc"

Output

1