알고리즘/LeetCode
LeetCode 풀기 - 20. Valid Parentheses
앤테바
2021. 10. 31. 12:01
반응형
https://leetcode.com/problems/valid-parentheses/
Valid Parentheses - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제)
풀이 전략)
- 스택 자료구조 이용
솔루션1)
class Solution:
def isValid(self, s: str) -> bool:
end_parentheses = [')', ']', '}']
stack = []
stack.append(s[0])
for c in s[1:]:
if c in end_parentheses:
if len(stack) == 0:
return False
if c == ')' and stack.pop() != '(':
return False
elif c == ']' and stack.pop() != '[':
return False
elif c == '}' and stack.pop() != '{':
return False
else:
stack.append(c)
if len(stack) == 0:
return True
else:
return False
솔루션2)
- 스택과 hash 사용
class Solution:
def isValid(self, s: str) -> bool:
# Use stack, dict
d = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in d.values():
stack.append(c)
elif c in d.keys():
if len(stack) == 0 or stack.pop() != d[c]:
return False
return len(stack) == 0
반응형