[leetcode] 20. Valid Parentheses

 

https://leetcode.com/problems/valid-parentheses/

 

전형적인 stack 문제이다.

주어진 문자열의 처음부터 끝까지 순회하면서, 열린 부호를 stack 에 쌓는다.

순회 도중에 닫힌 부호를 만나면, stack 의 가장 마지막 값과 비교하여 쌍을 이루는지 확인한다.

쌍을 이루지 않으면 곧바로 False 를 반환한다.

마지막에 stack 에 열린 부호만 남아있는 경우, False 를 반환한다.

stack 이 비어있는데 닫힌 부호를 만나면, 무조건 쌍을 이루지 못하기 때문에 False 를 반환한다.

 

 

class Solution:
    def isValid(self, ss: str) -> bool:
        st = list()
        for s in ss:
            if s in ('(', '{', '[') : st.append(s)
            elif s == ')' :
                if len(st) == 0 or st[-1] != '(' : return False
                else : del st[-1]
            elif s == ']' :
                if len(st) == 0 or st[-1] != '[' : return False
                else : del st[-1]
            elif s == '}' :
                if len(st) == 0 or st[-1] != '{' : return False
                else : del st[-1]
        return len(st)==0

 

class Solution:
    def isValid(self, ss: str) -> bool:
        if(len(ss)<=1 or len(ss) % 2 == 1):
            return False

        q = []
        for s in ss:
            if(len(q)==0):
                if(s==')' or s==']' or s=='}'): return False
                q.append(s)
            elif(s==')' and q[-1]=='(') : q.pop()
            elif(s=='}' and q[-1]=='{') : q.pop()
            elif(s==']' and q[-1]=='[') : q.pop()
            else: q.append(s)
        return len(q)==0

 

---

 

 

< English (feedback by ChatGPT) >

 

 

This is a typical stack problem.

(This is a typical stack problem.)

 

We Iterate through the given string from the beginning to the end and store the open bracket into the stack.

(We iterate through the given string from beginning to end and push any opening brackets onto the stack.)

 

When encounter the close bracket, check if it makes a pair with the last value of the stack.

(When we encounter a closing bracket, we check whether it forms a valid pair with the last value in the stack.)

 

If it doesn't make a pair, return False immediately.

(If it doesn’t form a pair, we return False immediately.)

 

The stack stores only the open brackets at last, return False. 

(If there are still opening brackets left in the stack at the end, we return False.)

 

If encounter the close bracket when the stack is empty, return False because it never makes a pair.

(Also, if we encounter a closing bracket while the stack is empty, we return False because it cannot be matched.)