Given a string 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.


Note that an empty string is also considered valid.

Example 1:


Input: "()"
Output: true


Example 2:


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


Example 3:


Input: "(]"
Output: false


Example 4:


Input: "([)]"
Output: false


Example 5:


Input: "{[]}"
Output: true

Difficulty: introductory

Starter code:

class Solution:
    def isValid(self, s: str) -> bool:
        

Solutions:
class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         stack = []
         dict = {"]":"[", "}":"{", ")":"("}
         
         for i in s:
             if i in dict.values():
                 stack.append(i)
             elif i in dict.keys():
                 if stack == [] or dict[i] != stack.pop():
                     return False
             else:
                 return False
         return not stack

class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
         for parenthese in s:
             #print(parenthese)
             if parenthese in lookup.keys():
                 stack.append(parenthese)
             elif len(stack) == 0 or lookup[stack.pop()] != parenthese:
                 return False
             #print(stack)
         return len(stack) == 0

class Solution:
     
     import re
     
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         
         while(s!=""):
             len_orig = len(s)
             s = s.replace('()', '')
             s = s.replace('[]', '')
             s = s.replace('{}', '')
             if len(s) == len_orig:
                 return False
     
         return True
             


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         l=list(s)
         stack=[]
         if l[0]==")" or l[0]=="]" or l[0]=="}" or len(l)<2:
             return False
         else:
             stack.append(l[0])
             l=l[1:]
         while stack!=[] or l!=[]:
             if l==[]:
                 return False
             else:
                 if l[0]=="(" or l[0]=="[" or l[0]=="{":
                     stack.append(l[0])
                 else:
                     if stack==[]:
                         return False
                     elif stack[-1]=="(" and l[0]==")":
                         stack.pop()
                     elif stack[-1]=="[" and l[0]=="]":
                         stack.pop()
                     elif stack[-1]=="{" and l[0]=="}":
                         stack.pop()
                     else:
                         return False
                 l=l[1:]
 
 
         return True

class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         correct = ['()', '[]', '{}']
         out = ""
         a = s
         while self.contains(a, correct):
             for sym in correct: 
                 a = a.replace(sym, '')
         if len(a)==0:
             return True
         else: 
             return False
         
     def contains(self, st, chars):
         for ch in chars: 
             if ch in st: 
                 return True 
         return False


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         if len(s)==0:return True
         stack=[]
         for i in s:
             if i=='(' or i=='{'or i=='[':
                 stack.append(i)
             else:
                 if len(stack)==0:return False
                 j=stack.pop()
                 if (j=='('and i!=')')or(j=='['and i!=']')or(j=='{'and i!='}'):
                     return False
         return len(stack)==0


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         if len(s)%2 != 0:
             return(False)
         
         stack=[]
         for i in range(len(s)):
             stack.append(s[i])
             if stack[0] == ')' or stack[0] == ']' or stack[0] == '}':
                 return(False)
             if stack[-1] == ')' :
                 if stack[-2] =='(':
                     stack.pop()
                     stack.pop()
             elif stack[-1] == ']' :
                 if stack[-2] =='[':
                     stack.pop()
                     stack.pop()
             elif stack[-1] == '}':
                 if stack[-2] =='{':
                     stack.pop()
                     stack.pop()
         if stack == []:
             return(True)
         else:
             return(False)

class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         lefty = ['(', '{', '[']
         D = { ')':'(', '}':'{', ']':'[' }
         L = []
         for b in s:
             if b in lefty:
                 L.append(b)
             else:
                 if len(L)==0 or D[b]!=L.pop():
                     return False
         if len(L)!=0:
             return False
         else:
             return True


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         
         # ###method1
         # while  "()" in s or "[]" in s or "{}" in s:
         #     s = s.replace("()","").replace("[]","").replace("{}","")
         # return len(s)==0
         
         stack = []
         dict = {")":"(", "]":"[", "}":"{"}
         for char in s:
             if char in list(dict.values()):
                 stack.append(char)
             elif char in list(dict.keys()):
                 if stack==[] or dict[char] != stack.pop():
                     return False
             else:
                 return False
         return stack==[]
     
  


class Solution:
     
     # stack approach
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
 
         open_chars = set(['(', '[', '{'])
 
         # matching open char for given closing char
         open_match = {')':'(', ']':'[', '}':'{'}
 
         # open chars found in input with no matching
         # closing char yet
         open_stack = []
 
         for ch in s:
 
             if ch in open_chars:
 
                 open_stack.append(ch)
 
             else:
 
                 if not open_stack \
                     or open_stack[-1] != open_match[ch]:
 
                     return False
 
                 open_stack.pop()
 
         return not open_stack


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         while  "()" in s or "[]" in s or "{}" in s:
             s = s.replace("()","").replace("[]","").replace("{}","")
         return len(s)==0


class Solution:
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
         n = len(s)
         if n == 0:
             return True
         
         if n % 2 != 0:
             return False
             
         while '()' in s or '{}' in s or '[]' in s:
             s = s.replace('{}','').replace('()','').replace('[]','')
         
         if s == '':
             return True
         else:
             return False

class Solution:
     def isValid(self, s):
         while '()' in s or '{}' in s or '[]' in s:
             s = s.replace('{}','').replace('()','').replace('[]','')
         
         if s == '':
             return True
         else:
             return False
             
         """
         :type s: str
         :rtype: bool
         """


class Solution:
     
     # stack approach
     def isValid(self, s):
         """
         :type s: str
         :rtype: bool
         """
 
         open_chars = set(['(', '[', '{'])
 
         # matching open char for given closing char
         open_match = {')':'(', ']':'[', '}':'{'}
 
         # open chars found in input with no matching
         # closing char yet
         open_stack = []
 
         for ch in s:
 
             if ch in open_chars:
 
                 open_stack.append(ch)
 
             else:
 
                 if not open_stack \
                     or open_stack[-1] != open_match[ch]:
 
                     return False
 
                 open_stack.pop()
 
         return not open_stack