20.有效的括号

1.题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例:

输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false
输入: "{[]}"
输出: true

2.思路

分析题意得知，字符串中只能出现’(‘，’)’，’{‘，’}’，’[‘，’]’只能出现这几个字符，如果为有效括号的话，左括号肯定为相同类型的右括号闭合，且最后的左括号先闭合。我们可以利用LinkedList中的push与pop方法，当字符串中出现了( 、{ 、[ 这三种类型的任意一种，我们就将其对应的右半边括号push到list中。如果遇到了) 、} 、] 这三种，我们则到list中进行比对，利用pop方法，直到把整个字符串遍历完，返回结果。

    public boolean isValid(String s) {
        LinkedList<Character> list = new LinkedList();
        for (char c : s.toCharArray()) {
            if (c == '('){
                list.push(')');
            }else if (c == '['){
                list.push(']');
            }else if (c == '{'){
                list.push('}');
            }else if (list.isEmpty() || c != list.pop()){
                return false;
            }
        }
        return list.isEmpty();
    }

push():将元素插入到列表的前面（从首位插入）

pop():删除并返回列表的第一个元素