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

Explanation

There are 3 pair of parentheses:

'(' <=> ')' '{' <=> '}' '[' <=> ']'

Think about the case ‘{[]}’, it is not hard to figure out, we need a Stack to store the last valid left part of parentheses, when next char is valid right part, pop out the left part.

Another trivial optimization is, any input just contains these characters, so a valid parentheses string’s length should always be even, we can add a check at the beginning.

Time complexity: $O(N)$, space complexity: $O(N)$.

The worst space complexity happened when the input similar as: ‘((((((((((‘.

C++

#include<stack> usingnamespacestd;

classSolution { public: boolisValid(string s){ if(s.size()%2) returnfalse; stack<char> buf; for(size_t i = 0; i < s.size(); i++) { char t = s[i]; if(t == '(' || t == '{' || t == '[') buf.push(t); else { if(buf.empty()) returnfalse; char p = buf.top(); if((p == '(' && t == ')') || (p == '{' && t == '}') || (p == '[' && t == ']')) buf.pop(); else returnfalse; } } return buf.empty(); } };

Java

classSolution{ publicbooleanisValid(String S){ if(S.length() % 2 != 0) returnfalse; Stack<String> s = new Stack<String>(); for(char c : S.toCharArray()){ String cc = String.valueOf(c);

if(c == '{' || c == '(' || c == '[') s.push(cc);

else{ if(s.empty()) returnfalse; char top = s.peek().toCharArray()[0];

if( (top == '{' && c == '}') || (top == '(' && c == ')') || (top == '[' && c == ']') ){ s.pop(); } elsereturnfalse; }

} return s.empty(); } }

Python

For Python, we can use list replace stack, and also but a dict for clean code.

classSolution: defisValid(self, s: str) -> bool: iflen(s) % 2 != 0: returnFalse dic = {'(' : ')', '[' : ']', '{' : '}'} stack = [] g = dic.keys() for c in s: if c in dic.keys(): stack.append(c) else: if stack == []: returnFalse a = stack.pop() if c != dic[a]: returnFalse return stack == []