ตรวจสอบคำว่าถูกต้องหลังการแทนที่ (Check If Word Is Valid After Substitutions) ใน C++

โจทย์: กำหนดสตริง "abc" เป็น valid จาก valid string V ใดๆ สามารถแบ่ง V = X + Y ได้ (X หรือ Y อาจว่าง) แล้ว X + "abc" + Y ก็ valid ด้วย เช่น "abc", "aabcbc", "abcabc", "abcabcababcc" เป็น valid ส่วน "abccba", "ab", "cababc", "bac" เป็น invalid ต้องตรวจสอบว่าสตริง S ที่ให้มาถูกต้องหรือไม่

ตัวอย่าง

Input: "abcabcababcc"
Output: true (1)

แนวทางแก้ปัญหา (ใช้ Stack)

สร้าง stack st เก็บ char
วนลูปทุกตัวอักษรใน S:
- ถ้า stack ว่าง หรือตัวอักษรปัจจุบันไม่ใช่ 'c': push เข้า stack
- ถ้าเป็น 'c': push 'c' เข้า stack, แล้ว while stack size >= 3:
  - pop 3 ตัว: c, b, a
  - รวมเป็น string temp = a+b+c
  - ถ้า temp == "abc": ทิ้งไป (valid substring) และ continue
  - มิฉะนั้น: push กลับ a,b,c แล้ว break
คืน true ถ้า stack ว่าง, มิฉะนั้น 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; // valid "abc" found, discard
                    } else {
                        st.push(a); st.push(b); st.push(c);
                        break;
                    }
                }
            }
        }
        return st.empty();
    }
};

int main() {
    Solution ob;
    cout << (ob.isValid("abcabcababcc"));
}

Input

"abcabcababcc"