1. 首页
  2. LeetCode

每日一道 LeetCode (6):有效的括号

每日一道 LeetCode (6):有效的括号

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:有效的括号

题目来源:https://leetcode-cn.com/problems/valid-parentheses/

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

有效字符串需满足:

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

解题思路

解题思路?

啊呸,有个 P 的解题思路,我跟你们讲哦,这种题没见过,你就是想不出来。

我自己思索了几分钟以后,果断投降去看答案了,这玩意,不是我这种新手小白搞的定的。

结果,一看答案秒懂。

每日一道 LeetCode (6):有效的括号

整个解题思路是借用了数据结构「栈」的「先进后出」的特性。

首先第一件事情还是先思考清楚极限情况,比如如果是空字符串,是可以返回 true ,如果字符串长度是奇数,那么显然是无法满足左右括号的对应关系。

接下来就是核心问题,一个左括号一个右括号,中间还可能隔着千山万水,如何处理?

使用「栈」结构:

  • 遇到左括号就压入栈。
  • 遇到右括号就和栈顶的左括号比对,匹配失败直接返回 false 。
  • 如果匹配成功,则可能是嵌套在其它匹配括号中的,所以此时要将当前栈顶的左括号弹出。
  • 如果最后最终,栈中没有剩余元素,也就是没有剩下左括号,说明刚好完成匹配,括号字符串有效。否则匹配失败,括号字符串无效。

如果上面这一段不好理解,可以借助下面这个动图(来源:LeetCode):

每日一道 LeetCode (6):有效的括号

代码实现

有了上面的思路,写代码都是小事儿了,先看一个我自己写的,完全符合上面的逻辑:

public boolean isValid(String s) {
    if (s.length() == 0) return true;

    if (s.length() % 2 == 1) return false;

    Stack<Character> stack = new Stack<> ();

    for (int i = 0; i < s.length(); i++) {
        char charAt = s.charAt(i);

        // 如果是左括号,则把字符压入栈
        if (charAt == '(' || charAt == '{' || charAt == '[')
            stack.push(charAt);
        else {
            // 如果此时还有右括号而栈中已无左括号
            if (stack.isEmpty()) return false;
            // 获取栈顶的值
            char top = stack.peek();
            // 如果栈顶的值等于右括号,则出栈,否则返回 false
            if ((top == '{' && charAt == '}') || (top == '(' && charAt == ')') || (top == '[' && charAt == ']'))
                stack.pop();
            else
                return false;
        }
    }
    return stack.isEmpty();
}

每日一道 LeetCode (6):有效的括号

里面的注释已经比较清晰了,我就不多解释了。

接着我看了官方提供的答案,基本上思路和我的代码保持一致,只是把左右括号放入到了哈希表中,由哈希表来判断括号是否存在。

private Map<Character, Character> map;

// 初始化哈希表
public Solution() {
    this.map = new HashMap<> ();
    this.map.put(')', '(');
    this.map.put('}', '{');
    this.map.put(']', '[');
}

public boolean isValid_1(String s) {
    if (s.length() == 0) return true;

    if (s.length() % 2 == 1) return false;

    Stack<Character> stack = new Stack<> ();

    for (int i = 0; i < s.length(); i++) {
        char charAt = s.charAt(i);
        // 如果不是右括号,则把字符压入栈
        if (!this.map.containsKey(charAt)) {
            stack.push(charAt);
        } else {
            // 如果此时还有右括号而栈中已无左括号
            if (stack.isEmpty()) return false;
            // 获取栈顶的值
            char top = stack.peek();
            // 如果栈顶的值等于右括号,则出栈,否则返回 false
            if (top == this.map.get(charAt))
                stack.pop();
            else
                return false;
        }
    }
    return stack.empty();
}

每日一道 LeetCode (6):有效的括号

因为哈希表中的数据太少,而且寻址的次数也不够多,所以哈希表的方案看起来还比顺次匹配的的方案耗时高。

效率更高的方案有没有,当然有,直接使用数组模拟栈的入栈和出栈,这个时间是可以压缩在 1ms 以内的,执行时间可以在 Java 的提交中击败 100% 的用户,这个示例我就不写了,感兴趣的同学可以自己写写看。

在我翻答案的时候看到一个 1ms 的方案,这个方案是对我前面的那个 2ms 的代码的优化,有点意思,拿出来聊一下:

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

每日一道 LeetCode (6):有效的括号

这个方案就是在遇到左括号的时候往栈里面放一个对应的右括号,这么做的原因我猜测是为了好判断,只需要取出的时候和当前循环的右括号做一次 == 判断,如果相等就继续循环,不相等就直接返回 false 了。

不得不说这个方案的构思很巧妙,在已有的方案上做了相当极致的优化,把耗时进一步降低。果然姜还是老的辣,你大爷还是你大爷。

每日一道 LeetCode (6):有效的括号

果然是学无止境,希望各位刷 LeetCode 的同学,如果时间充足,也可以多看看不同的答案,对开阔思路和视野真的是相当有帮助。

顺便吐槽下:想到这些方案的大神太 TM 变态了,这个脑回路和常人差的太远了,能用数组把耗时压到 1ms 以内我能接受,但是能把栈这种数据结构的方案优化到 2ms 以内,这个我是真的服。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code