20. 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.

思路: 建是否括号匹配, 可以用stack来做.
1. 遍历给定的字符串,针对每个字符char, 当char等于'(‘,”{“,'[‘的时候,把char压入stack.
2. 当char等于’)’,’}’,’]’的时候,把stack栈顶元素pop出来,跟char比较看是否是一对。这里要注意几个情况的判断: 1. stack.isEmpty(), 为空的话,返回false. 2. sc == ‘)’ && stack.pop() != ‘(‘, 返回false.同理其他的几个括号.
3.最后还要判断下最后stack是否为空. 不为空,返回false。

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character sc = s.charAt(i);
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.push(sc);
            }
            if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {
                if (stack.isEmpty()) return false;
                if (sc == ')' && stack.pop() != '(') return false;
                if (sc == '}' && stack.pop() != '{') return false;
                if (sc == ']' && stack.pop() != '[') return false;
            }
        }
        return stack.isEmpty();

    }
}
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