[LeetCode] 20. Valid Parentheses

Posted on | In

Problem

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:

1
2
Input: "()"
Output: true

Example 2:

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

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

Explanation

  1. Using stack.

  2. Iterate the input string, if the current character is open symbol, we put its corresponding closed symbol to the stack. If the character is closed symbol, we compare the pop element of the stack with the current character. If they are not equal, we return false, or if the stack is empty, we return false. At the end If the stack is empty, we return true, otherwise, we return false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValid(String s) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (arr[i] == '(') {
                stack.push(')');
            } else if (arr[i] == '[') {
                stack.push(']');
            } else if (arr[i] == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != arr[i]) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}