[LeetCode] – Stack – Valid Parentheses

Problem:

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.

Method:

Use stack. If encounter a left parentheses, push into stack. If encounter a right parentheses, check if it equals with the peek.

Several details:

1. Stack<Character> is correct, but Stack<char> is wrong

2. Use ‘==’ to check chars equal or not. Use ‘isEqual()’ to check Strings equal or not.

Code:

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return false;
        Stack<Character> stack = new Stack<Character>();  
        // Please note that you can't write 'char'. Generics has to be object type.
        stack.push(s.charAt(0));
        for (int i = 1; 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.isEmpty() && stack.peek() == '('){
                    stack.pop();
                }else{
                    return false;
                }
            }else if (s.charAt(i) == '}'){
                if (!stack.isEmpty() && stack.peek() == '{'){
                    stack.pop();
                }else{
                    return false;
                }
            }else{
                if (!stack.isEmpty() && stack.peek() == '['){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if (stack.isEmpty()) return true;
        else return false;
    } 
}