สมมติว่าเราได้รับสตริง "abc" ที่ถูกต้อง ดังนั้นจากสตริง V ที่ถูกต้องใดๆ เราสามารถแบ่ง V ออกเป็นสองส่วน X และ Y โดยที่ X + Y จะเหมือนกับ V (X หรือ Y อาจว่างเปล่า) จากนั้น X + "abc" + Y ก็ใช้ได้เช่นกัน ตัวอย่างเช่น S ="abc" ตัวอย่างของสตริงที่ถูกต้อง ได้แก่ "abc", "aabcbc", "abcabc", "abcabcababcc" และตัวอย่างของสตริงที่ไม่ถูกต้อง ได้แก่ "abccba", "ab", "cababc", "bac" เราต้องตรวจสอบว่าจริงหรือไม่ก็ต่อเมื่อสตริงที่กำหนด S ถูกต้อง
ดังนั้นหากอินพุตเป็นเหมือน “abcabcababcc” แสดงว่าถูกต้อง ดังนั้นเอาต์พุตจะเป็นจริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดสแต็ก st
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาด S
-
หาก 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” ให้ทำซ้ำต่อไป
-
อย่างอื่น
-
ดัน a แล้วก็ b แล้วก็ c เป็น st แล้วทำลายลูป
-
-
-
-
คืนค่า จริง เมื่อ st ว่างเปล่า มิฉะนั้น คืนค่า เท็จ
-
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
