这是我参与更文挑战的第17天，活动详情查看：更文挑战

前言

力扣第二十题 有效的括号 如下所示：

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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

一、思路

看到这种一一对应匹配的问题，我第一反应就是想到用栈来实现。因为栈的数据结构是先进后出的，非常适合这种类型的问题。

tips：为了方便描述，左括号指的是 '(' '{' '['，右括号指的是 ')' '}' ']'

我们只需要在碰到左括号时候进栈，碰到可匹配的右括号出栈。如果最后栈不为空说明不是有效的字符串，如果为空则是有效的字符串。

图解进出栈

在这里我们举一个稍微复杂点的例子，假设字符串 s = '((())()}'，具体的步骤如下图所示。

图片解释：
橘黄色部分为字符串，未填写的部分说明已经消耗掉了（可能是入栈或则用来匹配左括号）
绿色部分为栈
数字表示元素在栈或者字符串中的位置

因为碰到左括号就进栈，所以前三个字符刚开始都会入栈，如下图所示：

s 中的第四个元素是右括号，会看一下是否能和栈顶的元素匹配，如果匹配就会出栈。此时第四个元素为 )，栈顶元素为 (，栈顶出栈。如下图所示：

s 的第五个元素依旧是右括号且可以与栈顶匹配，继续出栈。如下图所示：

s 的第六个元素为左括号，入栈即可

s 的第七个元素是右括号且可以与栈顶匹配，继续出栈。如下图所示：

s 的第八个元素是右括号，但无法与栈顶匹配。只要出现这种无法匹配的情况，说明这个字符串就是不正确的。因为第 2 ~ 6都是可以匹配的，如果 1 ~ 8两个位置无法匹配，则不为有效字符串。

二、实现

实现方案

实现代码

    public boolean isValid(String s) {
        String leftBrackets = "{[(";
        String rightBrackets = "}])";
        Stack<String> stack = new Stack<>();
        for (int i=0; i<s.length(); i++) {
            String temp = s.substring(i, i+1);
            // 含有左括号，入栈
            if (leftBrackets.contains(temp)) {
                stack.push(temp);
            }
            // 是右括号，出栈
            if (rightBrackets.contains(temp)) {
                if (stack.empty())
                    return false;
                int index = rightBrackets.indexOf(temp);
                String currentStr = stack.pop();
                if (!currentStr.equals(leftBrackets.substring(index, index+1))) {
                    return false;
                }
            }
        }
        return stack.empty();
    }
复制代码

测试代码

    public static void main(String[] args) {
        new Number20().isValid("{()()]");
    }
复制代码

结果

结果不是很理想，只击败了30%

优化方案

参考了一下用时较短的解法，使用了char代替String，并且去除了String.indexof()

代码实现

    /**
     * 使用栈来实现
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            // 为左括号，入栈
            if ('(' == c || '[' == c || '{' == c) {
                stack.push(c);
            } else {    // 右括号出栈
                // 如果栈为空，直接返回false
                if (stack.empty())
                    return false;
                if (!isMatch(stack.pop(), c)) {
                    return false;
                }

            }
        }
        return stack.empty();
    }

    public boolean isMatch(char left ,char right) {
        switch (left) {
            case '{':
                return '}' == right;
            case '(':
                return ')' == right;
            case '[':
                return ']' == right;
            default:
                return false;
        }
    }
复制代码