Chương trình C ++ để kiểm tra xem chuỗi đã cho có xấu hay không

Giả sử chúng ta có một chuỗi S với n ký tự. S chứa các ký tự tiếng Anh viết thường và ký tự ')'. Chuỗi không hợp lệ, nếu số ký tự ')' ở cuối lớn hơn số ký tự còn lại. Chúng ta phải kiểm tra xem S có xấu hay không.

Vì vậy, nếu đầu vào giống như S ="fega))))))", thì đầu ra sẽ là True, bởi vì điều này là xấu vì có 4 chữ cái và 6 ').

Các bước

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

ans := 0
n := size of S
i := n - 1
while (i >= 0 and S[i] is same as ')'), do:
   (decrease i by 1)
z := n - 1 - i
ans := 2 * z - n
if ans > 0, then:
   return true
Otherwise
   return false

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;

bool solve(string S) {
   int ans = 0;
   int n = S.size();
   int i = n - 1;
   while (i >= 0 && S[i] == ')')
      i--;
   int z = n - 1 - i;
   ans = 2 * z - n;
   if (ans > 0)
      return true;
   else
      return false;
}
int main() {
   string S = "fega))))))";
   cout << solve(S) << endl;
}

Đầu vào

"fega))))))"

Đầu ra

1