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.

Thinking:

Assumption: {[()]}() is valid.

Since there are only brackets in the string, we can easily make assumption that if the length of the string is not an even number, there must be a lonely parenthesis that is not valid.

Look at the pattern, if we have one opening bracket, then if it is valid, there must be a closing bracket. And if it is valid, the closing bracket is gonna be checked after everything is checked in this corresponding bracket. Therefore it is a FIFO behavior, because we’re always checking the closest correspondence. Therefore using a stack to check which one is nearest is ideal. At the end, we just need to check if there is anything left in the stack.

 

 


public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() ==0) return true;
        if (s.length() % 2 != 0) return false;
        
        Stack stack = new Stack();
        Map map = new HashMap();
        
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        
        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            Character correspondence = map.get(current);
            if (!stack.empty() && current == stack.peek()) {
                stack.pop();
            } else if (correspondence != null) {
                stack.push(correspondence);
            } else {
                return false;
            }
        }
        
        return stack.empty();
        
        
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s