-
Notifications
You must be signed in to change notification settings - Fork 73
/
brackets.py
55 lines (44 loc) · 1.46 KB
/
brackets.py
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
"""
A string S consisting of N characters is considered to be properly nested
if any of the following conditions is true:
S is empty;
S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
def solution(S)
that, given a string S consisting of N characters,
returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given
S = "([)()]", the function should return 0, as explained above.
Assume that:
N is an integer within the range [0..200,000];
string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N)
(not counting the storage required for input arguments).
"""
CLOSING = {
']': '[',
')': '(',
'}': '{',
}
def solution(S):
stack = []
for ch in S:
if ch in CLOSING:
if not stack:
# encountered closing bracket but stack is already empty!
return 0
last = stack.pop()
if last != CLOSING[ch]:
# wrong bracket encountered
return 0
else:
stack.append(ch)
if stack:
# there are still opened brackets on a stack
return 0
else:
return 1