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.

题目翻译

给出一个字符串仅包含如下字符'('，')'，'{'，'}'，'['和']'，判断输入的字符串是否有效。

所有括号以正确的顺序闭合该字符串即为有效，比如"()"和"()[]{}"都是有效的字符串，但是"(]"和"([)]"都是无效的字符串。

解题方案

标签： String

思路：

• 使用栈结构来存储
• 遍历字符串，当出现 ( , { , [ 这三个字符的时候，将字符压入栈中
• 否则则代表出现的是 ) , } , ] 这三个字符
• 当 ) , } , ] 这些字符时先判断栈内是否为空，如果为空，说明没有与之匹配的字符存在，则返回false
• 如果不为空，则判断是否栈顶元素与当前出现的字符匹配，即是否满足 () {} [] 两两匹配，如果不匹配则返回false
• 遍历结束后如果栈内还有元素，说明匹配不完全，则返回false，如果为空则匹配完全，返回true

代码：

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

参考资料

同步发表于 http://blog.csdn.net/grape875499765/article/details/78200994