Amazon-Valid Parentheses (Easy)

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: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution:

public boolean isValid(String s) {
        if(s==null|s.length()==0) return true;
        char[] sc=s.toCharArray();
        Stack<Character> path=new Stack<>();
        for(char c:sc){
            if(c=='('||c=='['||c=='{')
                path.push(c);
            else if(path.size()>0){
                if(c==')'&&path.peek()=='('){
                    path.pop();
                }else if(c==']'&&path.peek()=='['){
                    path.pop();
                }else if(c=='}'&&path.peek()=='{'){
                    path.pop();
                }else{
                    return false;
                }
                
            } else {
                return false;
            }
        }
        if(path.size()==0)
            return true;
        else
            return false;
    }

时间复杂度：O(n)
空间复杂度：O(n)

比较基础，只是题目中的要求基本上Example都给的很明确了，栈不为空，说明不匹配，栈为空时，第一个字符不是左括号的说明不匹配。其实还有一种简单的方法，别人写的，很灵性。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    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();
}

思路就是只入后括号，再弹出。

测试用例
Case 1:

[
false

Case 2:

]
false