LeetCode题解

LeetCode020:有效的括号

2019-02-28  本文已影响2人  大大纸飞机

题目介绍

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

  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

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

上一篇 下一篇

猜你喜欢

热点阅读