Leetcode/各大家 -- 20. Valid Parentheses(Stack)

20. Valid Parentheses(Stack)

• Difficulty: Easy

https://leetcode.com/problems/valid-parentheses/

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Company：  Airbnb Facebook Twitter Zenefits Amazon Microsoft Bloomberg

思路： - when meeting open bracket [,{,(  push it to stack
          - when meeting closing one, pop the stack to check if match, stack should be empty if valid
          - edge case: '[' ,']]'

Complexity: Time O(N) Space O(N)

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            char cur = s.charAt(i);
            if(cur == '('||cur=='{'||cur=='['){
                st.push(cur);
            } else{
                if(st.empty())return false;
                char pre = st.pop();
                if((pre=='('&&cur ==')')|| (pre=='{'&&cur =='}')||(pre=='['&&cur ==']'))continue;
                return false;
            }
        }
        if(st.empty()) return true;
        return false;
    }
}