โจทย์: กำหนดสตริง s ประกอบด้วย '(', ')' และตัวอักษรภาษาอังกฤษพิมพ์เล็ก ต้อง ลบวงเล็บน้อยที่สุด ( '(' หรือ ')' ในตำแหน่งไหนก็ได้) เพื่อให้สตริงวงเล็บที่ได้เป็น valid และคืนค่าสตริงที่ถูกต้องใดๆหนึ่ง
สตริงวงเล็บถูกต้อง (valid) เมื่อ:
- เป็นสตริงว่าง หรือมีแต่ตัวอักษรพิมพ์เล็ก
- เขียนในรูป AB (A ต่อ B) โดย A และ B เป็น valid strings
- เขียนในรูป (A) โดย A เป็น valid string
ตัวอย่าง
Input: "a)b(c)d" Output: "ab(c)d"
แนวทางแก้ปัญหา (ใช้ Stack)
- สร้าง stack
stเก็บ index ของ '(' - วนลูปทุกตัวอักษรใน s:
- ถ้าเป็น '(' : push index เข้า stack
- ถ้าเป็น ')' : ถ้า stack ไม่ว่าง pop ออก, มิฉะนั้นทำเครื่องหมาย s[i] = '*' (จะลบภายหลัง)
- หลังวนลูป: index ที่เหลือใน stack คือ '(' ที่ไม่มีคู่ ทำเครื่องหมาย '*' ทุกตัว
- สร้างสตริงคำตอบโดยข้ามตัวอักษร '*'
ตัวอย่างโค้ดเต็ม
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> st;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '(') st.push(i);
else if(s[i] == ')') {
if(!st.empty()) st.pop();
else s[i] = '*'; // mark for removal
}
}
while(!st.empty()) {
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++) {
if(s[i] != '*') ans += s[i];
}
return ans;
}
};
int main() {
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}
Input
"a)b(c)d"
Output
ab(c)d
