Question

link

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.

Stats

Frequency 5
Diffficulty 2
Adjusted Difficulty 3
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Either stack or string would work.

Solution

The code is easy.

My code

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<Character>();
        // process s char by char
        for (char c: s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    // eg. input = "())))"
                    return false;
                }
                char top = stack.pop();
                if (Math.abs(top - c) > 2) {
                    // parentheses does not match
                    return false;
                }
            }
        }
        // after this, stack should be empty (if parentheses valid)
        return stack.isEmpty();
    }
}