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: "()" |
Solution
Use Stack.Each time when we meet the left ([,{,(
) symbol, we have to put into the stack and when we meet the right symbol we have to pop out and to see if it works. Of course, if the stack is empty and then put the right symbol to verify and we just need to return false. At the end, the stack should be empty.
Code
1 | // time:O(n) |