LeetCode第20题：有效的括号

本文首发于公众号「猿天罡」，转载请注明出处，谢谢！

本题源自LeetCode，题号20。

1.题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

2.解题思路

题目的意思是：给定一串括号组成的字符串，让我们判断括号闭合顺序和类型是否正确。

从示例中也可以明白题意。

我们可以用栈结构来解决这道题。栈是先进后出的一种数据结构。如果我们把一些数字顺序存进栈结构中，那么我们取出数字的顺序是和存储顺序相反的。

为了更好地理解栈这种结构，我简单地画了张图。

栈

我们把数字1,2,3,4依次存储到栈的过程称作进栈/压栈，把4,3,2,1依次取出的过程称作出栈/弹栈。

算法具体过程：

1. 初始化栈S。

2. 一次处理给定字符串中的每一个括号。

3. 如果遇到开括号，我们就将其压栈。

4. 如果遇到闭括号，我们就检查栈顶元素（即上图所示栈中最上面的元素）。

   1. 如果栈顶元素是一个相同类型的左括号，那么我们将把它从栈中弹出来并继续处理。

   2. 否则，这表示给定字符串无效。

5. 如果到最后栈中还剩下元素，也表示给定字符串无效

3.算法动画

假设给定的字符串是{[()]}，依照上面的算法，运行过程如下图。

有效的括号

如果给定的字符串是{[(]]}，依照上面的算法，运行过程如下图。

无效的括号

4.代码实现

由于个人精力有限，暂时只提供Java语言代码实现。只要理解了本算法的思想，你也能用其他语言实现出来，这也是对个人代码能力的锻炼。

class Solution {
    private Map<Character, Character> map;

    public Solution() {
        this.map = new HashMap<Character, Character>();
        this.map.put(')', '(');
        this.map.put(']', '[');
        this.map.put('}', '{');
    }

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (this.map.containsKey(c)) { // 是闭括号
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (topElement != this.map.get(c)) // 括号不匹配
                    return false;
            } else { // 开括号
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

5.结语

说到令我们计算机专业最头疼的学科是啥，我猜十有八九会有人投「数据结构」一票，有的算法代码虽然十分简短，可是学起来真的会让人头秃。

除了怀着对计算机行业前辈们的无限憧憬以外，对算法我们其实是敬畏的。

我想，如果能用动画的方式去展示算法运行的过程却是极好的。这样不管是学习还是面试只要脑海中记住动画，心中大体就有了思路。

如果这篇文章对您有所帮助，欢迎点赞、转发加收藏啦~

或许您有任何疑问，可以扫描下方二维码与我联系，感谢您的阅读，我们下期再见。

猿天罡