Valid Parentheses

Question

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

Solution

def isValid(s):
  brackets = {"(": ")", "[": "]", "{": "}"}
  
  if s == "":
    return True
  
  if len(s) % 2 != 0:
    return False
  
  if s[0] not in brackets:
    return False
  
  i = 0
  while i < len(s):
    if s[i] == brackets[s[0]]:
      s_sub1 = s[1:i]
      s_sub2 = s[i+1: ]
      res = isValid(s_sub1) and isValid(s_sub2)
      return res
    i += 1
    
  res = False
  return res

  
s = "(([]){})"
isValid(s)

## False

This is wrong answer. The expected answer is True.

Change the idea. Use stack:

Save the open brack in stack, and delete it when comes a closed bracket.

def isValid2(s):
  stack = []
  h_map = {"(": ")", "[": "]", "{": "}"}
  for parentheses in s:
    if parentheses in h_map:
      stack.append(h_map[parentheses])
    elif len(stack) == 0 or stack.pop() != parentheses:
      return False
  return len(stack) == 0

s = "(([]){})"
isValid2(s)

## True

Summary

• Be careful to observe the rules of valid parentheses.