-
Notifications
You must be signed in to change notification settings - Fork 10
/
Leetcode22.py
34 lines (34 loc) · 1.05 KB
/
Leetcode22.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
class Solution(object):
# solution 1 - 时间复杂度: O(N)- 空间复杂度: O(N)
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
leftP = '([{'
rightP = ')]}'
stack = []
for char in s:
if char in leftP:
stack.append(char)
if char in rightP:
if not stack:
return False
tmp = stack.pop()
if char == ')' and tmp != '(':
return False
if char == ']' and tmp != '[':
return False
if char == '}' and tmp != '{':
return False
return stack == []
# - 时间复杂度: O(N^2)- 空间复杂度: O(N)
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
while '[]' in s or '()' in s or '{}' in s:
s = s.replace('[]', '').replace('()', '').replace('{}', '')
return len(s) == 0