L20 Valid Parentheses

stack

Problem

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:

Input: "()" Output: true Example 2:

Input: "()[]{}" Output: true Example 3:

Input: "(]" Output: false Example 4:

Input: "([)]" Output: false

Solution

use stack. The basic idea is to push the right parentheses into the stack each time when we encounter left ones. And if a right bracket appears in the string, we need check if the stack is empty and also whether the top element is the same with that right bracket. If not, the string is not a valid one.

At last , we also need to check if the stack is empty. Because if not, such as '((', there are two left parentheses, the stack will still hold two left chars.

TC: O(n) n is the length of the string

SC: O(n)

public boolean isValid(String s){
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()){
        if(c =='(') stack.push(')');
        else if(c == '[') stack.push(']');
        else if(c == '{') stack.push('}');
        else if(stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();  
}