Valid Parentheses

, , , , ,

Question

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

Note that an empty string is also considered valid.

Example

1
2
3
4
5
Input: "()"
Output: true

Input: "([)]"
Output: false

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// time:O(n)
// space:O(n)
public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '{') {
                stack.push('}');
            } else if (ch == '[') {
                stack.push(']');
            } else {
                if (stack.isEmpty() || stack.pop() != ch) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }