020.md

20. Valid Parentheses

Solution 1 (O(n))

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