(Medium) Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 

An input string is valid if: 

Open brackets must be closed by the same type of brackets. 

Open brackets must be closed in the correct order. 

Every close bracket has a corresponding open bracket of the same type. 

 

Example 1: 

Input: s = "()" 

Output: true 

 

Example 2: 

Input: s = "()[]{}" 

Output: true 

 

Example 3: 

Input: s = "(]" 

Output: false

 

* 단순히 괄호가 열리고 닫히기만 하면 된다

Example 4: 

Input: s = "([)]" 

Output: false

 

문제 :

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

풀이

# 핵심은 괄호 쌍을 맵핑하는것

# 추가 핵심은 스택을 써야한다는 것

 

dic = {')':'(', '}':'{', ']':'['} 

stack = []

 

for char in s: 

    if char in dic:

        if len(stack) == 0: # case : "]" 

            return False

        else:

            if dic[char] == stack[-1]: # 스택의 마지막 값을 의미

                stack.pop()

            else:                    # case : "(])" 

                return False

    else:

        stack.append(char)

 

return len(stack) == 0

 

# 아래와같이 리팩토링 가능.

for char in s:

    if char in dic:

        if stack and dic[char] == stack[-1]:

            stack.pop()

        else:

            return False

    else:

        stack.append(char)

return not stack

 

만약 모든 Example 4 도 True여야 한다면 코드는 아래와같이 짜야한다.

        dic = {'(':')','{':'}','[':']'}
        idx = len(s) - 1
        stack = []
        temp = ''

        for el in s:
            stack.append(el)

        if len(stack) % 2 == 1:
            return False

        while stack:
            
            temp = stack.pop()
            print(stack)
            for i in range(len(stack)-1, -1, -1):                
                if stack[i] in dic.keys() and dic[stack[i]] is temp:
                    stack.pop(i)
                    break
                if stack[i] in dic.keys() and dic[stack[i]] is not temp:
                    return False                
        return True