Tuesday, February 11, 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:
When met brackets questions, stack-based solution seems to be a good choice.
public class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0 || s.length() % 2 != 0) return false;
        Stack stack = new Stack();
        for(int i = 0; i < s.length(); i++){
            int cur = getIndex(s.charAt(i));
            if(cur == getIndex('(') || cur == getIndex('[') || cur == getIndex('{')) {
                stack.push(cur);
            }
            else{
                if(stack.isEmpty()) return false;
                int out = stack.pop();
                if (cur - out != 1) return false; //doesn't match
            }
        }
        if(stack.isEmpty()) return true; 
        else return false;
    }
    public int getIndex(char c){
        char[] symbols = {'(',')','[',']','{','}'};
        for(int i = 0; i < symbols.length; i++){
            if(symbols[i] == c) return i;
        }
        return -1;
    }
}

No comments:

Post a Comment