题目介绍

题目：有效的括号
描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1:
输入: "()"
输出: true

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

示例 3:
输入: "(]"
输出: false

示例 4:>
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

解析

括号有效的标准是每一个左括号对应一个右括号，右括号不能打头，且每个右括号之前要么还是右括号，要么就是和它匹配的左括号。

可以发现，从一个有效的括号字符串中去除一对括号后，剩余部分还是有效的括号字符串。那么我们就可以像玩消除游戏一样，每遇到一个右括号，就消除一对括号，直到没有右括号为止。如果最后所有的左括号都被消除了，那它就是一个有效的括号字符串。

以上的思路用栈来操作十分合适，所以我们的代码如下所示：

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    int i = 0;
    int len = s.length();
    while (i<len) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }else{
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.peek();
            if (top == '(' && c==')' || top=='[' && c==']' || top=='{' && c=='}') {
                stack.pop();
            }else{
                return false;
            }
        }            
        i++;
    }

    return stack.isEmpty();
}

总结

LeetCode上和括号相关的题目有好几个，这只是开胃菜，权当让大家练练手。如果你认为此题目过于简单，那么试试下一题吧。

相关源码已经上传到我的Github。

下题预告

题目：括号生成
描述：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
    "((()))",
    "(()())",
    "(())()",
    "()(())",
    "()()()"
]

---

本文到此就结束了，如果您喜欢我的文章，可以关注我的微信公众号： 大大纸飞机

或者扫描下方二维码直接添加：

公众号

您也可以关注我的github：https://github.com/LtLei/articles

编程之路，道阻且长。唯，路漫漫其修远兮，吾将上下而求索。