Valid Parentheses

Problem: Valid Parentheses

We can use a stack to maintain left parentheses and pop the stack if matching met. If they are valid all elements in stack should be popped out appropriately.

Code in Python:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if c == "(" or c == "[" or c == "{": stack.append(c)
            elif c == ")":
                if not stack or stack.pop() != "(": return False
            elif c == "]":
                if not stack or stack.pop() != "[": return False
            elif c == "}":
                if not stack or stack.pop() != "{": return False
        return not stack

Code in Java:

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) == ')') {
                if (stack.size() == 0 || stack.pop() != '(')
                    return false;
            } else if (s.charAt(i) == '}') {
                if (stack.size() == 0 || stack.pop() != '{')
                    return false;
            } else if (s.charAt(i) == ']') {
                if (stack.size() == 0 || stack.pop() != '[')
                    return false;
            }
        }

        if (stack.size() != 0) {
            return false;
        } else {
            return true;
        }
    }
}