소프트웨어에 대한 모든 것

LeetCode 풀기 - 20. Valid Parentheses 본문

알고리즘/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

 

반응형

'알고리즘 > LeetCode' 카테고리의 다른 글

LeetCode 풀기 - 155. Min Stack  (0) 2021.11.02
LeetCode 풀기 - 231. Power of Two  (0) 2021.11.02
LeetCode 풀기 - 136. Single Number  (0) 2021.10.31
LeetCode 풀기 - 771. Jewels and Stones  (0) 2021.10.29
LeetCode 풀기 - 226. Invert Binary Tree  (0) 2021.10.29
'알고리즘/LeetCode' Related Articles more
Comments