deeprun

Valid Parentheses

 문제 설명

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

 제한 사항

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 입출력 예

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 Python 코드

Python code 

class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      dic = {'(':')',
             '{':'}',
             '[':']'
            }
 
      for char in s:
          if char in dic.keys():
              stack.append(char)
 
          elif stack == [] or char != dic[stack.pop()] :
              return False
 
      return stack ==[]

* 참고 링크 : https://chaerim-kim.github.io/data%20structures%20and%20algorithms/ValidParentheses/

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        brackets={'}':'{',')':'(',']':'['}
        for bracket in s:
            if bracket in brackets.values(): #Opening bracket 
                stack.append(bracket)
            else:# Closing bracket
                if stack and brackets[bracket]==stack[-1] :  
                    stack.pop()
                else: 
                    return False
        
        if stack:
            return False
        return True

* 참고 링크 : https://velog.io/@kgh732/Python-%EC%9C%BC%EB%A1%9C-%ED%91%B8%EB%8A%94-Leetcode20.-Valid-Parentheses

class Solution: 
	def isValid(self, s: str) -> bool: 
    	s_list = list(s)
        
        answer = True 
        
        stack = [] 
        
        for s in s_list: 
        	if s == '[' or s == '(' or s == '{': 
            	stack.append(s) 
            elif len(stack) != 0: 
            	if (s == ']' and stack[-1] == '[') or (s == '}' and stack[-1] == '{') or (s == ')' and stack[-1] == '('): 
                	stack.pop() 
                else: 
                    answer = False 
                    break 
            else: 
            	answer = False 
                break 
                
        if len(stack) != 0: 
        	answer = False 
        return answer

* 참고 링크 : https://somjang.tistory.com/entry/leetCode-20-Valid-Parentheses-Python

C++ 코드

C ++ code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for(int i = 0; i < s.size(); i++) {
            if(s.at(i) == '{' || s.at(i) == '(' || s.at(i) == '[')      st.push(s.at(i));
            else {
                if(st.empty())      return false;
                else {
                    if((s.at(i) == '}' && st.top() != '{') || (s.at(i) == ')' && st.top() != '(') 
                        || (s.at(i) == ']' && st.top() != '['))
                            st.push(s.at(i));
                    else    st.pop();
                }
            }   
        }
        
        return st.empty();
    }
};

* 참고 링크 : https://m.blog.naver.com/tac1994/221839649888

 출처

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