Friday, March 28, 2014

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.
Solution 1:
public class Solution {
    public boolean isValid(String s) {
        Stack<character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.empty() && match(stack.peek(), s.charAt(i)))
                stack.pop();
            else
                stack.push(s.charAt(i));
        }        
        return stack.empty();
    }
    
    public boolean match(char a, char b) {
        return (a=='(' && b == ')') || (a=='{' && b == '}') || (a=='[' && b == ']');
    }
}
Solution 2:
public class Solution {
    public boolean isValid(String s) {
        Stack<character> stack = new Stack<>();

        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (!stack.empty() && match(stack.peek(), chars[i]))
                stack.pop();
            else
                stack.push(chars[i]);
        }     
        return stack.empty();
    }
    
    public boolean match(char a, char b) {
        return (a=='(' && b == ')') || (a=='{' && b == '}') || (a=='[' && b == ']');
    }
}

No comments:

Post a Comment