Bổ sung dấu ngoặc nhọn tối thiểu trong C ++

Giả sử chúng ta có một chuỗi s chỉ chứa '(' và ')', chúng ta phải tìm số lượng dấu ngoặc nhỏ nhất có thể được chèn vào để làm cho chuỗi cân bằng.

Vì vậy, nếu đầu vào là "(())) (", thì đầu ra sẽ là 2 là "(())) (", điều này có thể được cân bằng như "((())) ()".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• :=0, cnt:=0

• để khởi tạo i:=0, khi i

  • nếu s [i] giống với '(', thì -

    • (tăng o lên 1)

  • Nếu không

    • nếu o khác 0 thì -

      • (giảm o đi 1)

    • Nếu không

      • (tăng cnt lên 1)

• trả về cnt + o

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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("(()))("));
}

Đầu vào

Input:
"(()))("

Đầu ra

2