问题描述

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

代码实现

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

对给定的字符串进行遍历，当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们结合栈后进先出的特点，可以将这个左括号对应的右括号放入栈顶。
当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的右括号并判断它们是否相同。如果不相同，或者栈直接为空，那么字符串无效，返回 False。最后我们再判断是否还存在为出栈的元素，如果存在则返回False，不存在则返回True。