สมมติว่าเรามีสตริงที่มีเพียง '(' และ ')' เราต้องหาจำนวนวงเล็บขั้นต่ำที่สามารถแทรกได้เพื่อให้สตริงมีความสมดุล
ดังนั้น หากอินพุตเป็นแบบ "(()))(" ดังนั้นเอาต์พุตจะเป็น 2 เป็น "(()))(" ค่านี้จะสมดุลได้เหมือน"((()))()"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
:=0, cnt :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ถ้า s[i] เหมือนกับ '(' แล้ว −
-
(เพิ่มขึ้น o 1)
-
-
มิฉะนั้น
-
ถ้า o ไม่ใช่ศูนย์ ดังนั้น −
-
(ลดลง o 1)
-
-
มิฉะนั้น
-
(เพิ่มขึ้นอีก 1)
-
-
-
-
ส่งคืน cnt + o
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s) {
int o = 0;
int cnt = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '('){
o++;
} else {
if(o)
o--;
else
cnt++;
}
}
return cnt + o;
}
};
int main(){
Solution ob;
cout << (ob.solve("(()))("));
} อินพุต
Input:
"(()))(" ผลลัพธ์
2
