关于java:B站真题如何判断括号是否有效

本文已收录至我的 Github《算法图解》系列：https://github.com/vipstone/algorithm

明天要讲的这道题是 bilibili 往年的口试真题，也是一道对于栈的经典面试题。

通过后面文章的学习，我想很多敌人曾经看进去了，我接下来要写的是一个对于「算法图解」的系列文章，两头可能会交叉大量的其余类型的文章，但「算法和数据结构」会是我往年文章输入的重点内容。

我在写这个算法系列的时候会留神两个问题：

保障算法的解题思路大家都能看懂，因而我会以图片的模式进行思路解说，这样更直观、更易于了解；
在介绍完一个知识点之后，会进行大量的练习，以坚固所学的内容，比方当我讲完「栈」构造之后，我会围绕着「栈」做一系列的经典面试题练习。

学习算法最要害的是把握解题的思路，只有思路对了，编写代码只是工夫的问题。

咱们先来回顾一下往期对于「栈」的内容：

《动图演示：手撸堆栈的两种实现办法！》
《JDK 居然是这样实现栈的？》
《链表反转的两种实现办法，后一种击败了 100% 的用户！》
《算法图解：如何找出栈中的最小值？》

那么接下来，咱们就进入明天的正式内容 …

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

无效字符串需满足：

左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。
留神空字符串可被认为是无效字符串。

示例 1:

输出: “()”
输入: true

示例 2:

输出: “()[]{}”
输入: true

示例 3:

输出: “(]”
输入: false

示例 4:

输出: “([)]”
输入: false

示例 5:

输出: “{[]}”
输入: true

LeetCode 地址：https://leetcode-cn.com/problems/valid-parentheses

这道题考查的是就是验证括号的对称性，比方“([{}])”这种字符串就是正确的，应该返回 true，而“([{})]”这种字符串就是谬误的，应该返回 false。

从下面的题目能够看出，括号总共分为三类：小括号、中括号和大括号，那么咱们能够利用栈先进后出的个性，将所有右边的括号（“(”、“[”、“{”）先入栈，而后再碰到右括号时，让它与栈顶的元素进行匹配，比方当遇到“)”时，如果栈顶是“(”，则阐明匹配胜利，栈顶元素出栈再持续字符串循环的流程，如果匹配谬误就间接返回 false。

假如咱们要匹配字符串“(([]))”是否非法？那么执行流程就是这样的。

首先遇到右边括号，先入栈：

接下来又是右边括号，持续入栈：

而后又是右边括号，持续入栈：

接下来是左边括号，与栈顶元素匹配，“[]”为一对非法的括号，匹配胜利栈顶元素出栈：

接下来又是左边括号，与栈顶元素匹配，“()”为一对非法的括号，匹配胜利栈顶元素出栈：

接下来又是左边括号，与栈顶元素匹配，“()”为一对非法的括号，匹配胜利栈顶元素出栈：

当字符串循环完结并且栈为空栈时，则证实此字符串的括号匹配非法，最终的成果如下图所示：

那么接下来咱们就用代码来实现一下整个过程 …

public boolean isValid(String s) {int slen = s.length(); // 括号的长度
    if (slen % 2 == 1) { // 括号不是成对呈现间接返回 false
        return false;
    }
    // 把所有比照的括号存入 map，比照时用
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    // 定义栈，用于存取括号（辅助比拟）Stack<Character> stack = new Stack<>();
    for (int i = 0; i < slen; i++) { // 循环所有字符
        char c = s.charAt(i);
        if (map.containsKey(c)) {// 为左边的括号，如 ')'、'}' 等
            if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配
                return false;
            }
            stack.pop(); // 是一对括号，执行出栈（打消左右括号）} else { // 右边括号，间接入栈
            stack.push(c);
        }
    }
    return stack.isEmpty();}

咱们在 LeetCode 中提交一下代码，执行后果如下：

以上代码的 map 汇合是用于定义括号的匹配规定，比方“)”对应的匹配值是“(”，“]”的匹配值是“[”等，而后咱们再去循环待验证的字符串，遇到左括号间接入栈，遇到右括号让它与栈顶元素匹配，等到整个字符串循环完结，如果栈为空则阐明字符串的括号非法。

工夫复杂度：O(n)，遍历了一遍整个字符串。
空间复杂度：O(n)。

除了应用栈之外，咱们还能够应用借助 Java 中的 replace 办法来实现，咱们能够循环的打消字符串中的括号，比方将“()”或“[]”或“{}”循环得替换为空，最初在执行实现之后如果字符串为空，则阐明字符串中的括号是非法的，具体实现代码如下：

public boolean isValid(String s) {
        int len;
        do {len = s.length();
            // 打消成双成对的符号
            s = s.replace("()", "").replace("[]","").
                    replace("{}", "");
        } while (len != s.length()); // 不能再进行替换了，replace 办法没有替换任何字符
        return s.length() == 0;}

咱们在 LeetCode 中提交一下代码，执行后果如下：

从运行后果来看，二者的执行效率相差还是很显著的：

本文咱们讲了一道 bilibili 的口试真题，同时它也是栈的经典面试题，咱们能够借助栈的个性（先进后出）将所有的左括号入栈，当遇到右括号时让它与栈顶元素进行匹配，当字符串循环完结栈为空时，则阐明此字符串的括号是非法的。当然咱们在理论面试中，也能够应用 Java 的 replace 办法作为一个保底的实现计划，因为 replace 办法的实现绝对更简略一些，只是性能不那么好。

文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。

关于java:B站真题如何判断括号是否有效

题目

解题思路

实现代码一

代码解析

复杂度剖析

实现代码二

总结