/
main.cpp
64 lines (51 loc) · 1.61 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/// Source : https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/
/// Author : liuyubobobo
/// Time : 2022-01-28
#include <iostream>
#include <vector>
using namespace std;
/// Linear Scan
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.size();
if(n % 2 == 1) return false;
int open = 0, locked_num = 0;
for(int i = 0; i < n; i ++){
if(locked[i] == '1'){
locked_num ++;
if(s[i] == '(') open ++;
else open --;
}
int t = (i + 1) - locked_num;
if(open < 0 && t < abs(open)) return false;
}
open = 0, locked_num = 0;
for(int i = n - 1; i >= 0; i --){
if(locked[i] == '1'){
locked_num ++;
if(s[i] == ')') open ++;
else open --;
}
int t = (n - i) - locked_num;
if(open < 0 && t < abs(open)) return false;
}
return true;
}
};
int main() {
string s1 = "))()))", locked1 = "010100";
cout << Solution().canBeValid(s1, locked1) << endl;
// 1
string s2 = "())(()(()(())()())(())((())(()())((())))))(((((((())(()))))(";
string locked2 = "100011110110011011010111100111011101111110000101001101001111";
cout << Solution().canBeValid(s2, locked2) << endl;
// 0
string s3 = "((()(()()))()((()()))))()((()(()";
string locked3 = "10111100100101001110100010001001";
cout << Solution().canBeValid(s3, locked3) << endl;
// 1
return 0;
}