20. 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.

思路1：终于开始用Stack了

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

        return stack.empty();
    }
}

思路2：佩服佩服，脑洞实在大

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();
}

C++ code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (int i=0; i<s.size(); i++){
            if (s[i]=='('||s[i]=='['||s[i]=='{'){
                st.push(s[i]);
            }else if(s[i]==')' && !st.empty() && st.top()=='('){
                st.pop();
            }else if(s[i]==']' && !st.empty() && st.top()=='['){
                st.pop();
            }else if(s[i]=='}' && !st.empty() && st.top()=='{'){
                st.pop();
            }else{
                return false;
            }
        }
        return st.empty();
    }
};