力扣-20-有效的括号（简单）

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]‘ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]“
输出: false
示例 4:
输入: “([)]“
输出: false
示例 5:
输入: “{[]}”
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种解法

这题看示例就能明白，就是找对称，括号必须是成对出现，如果不是就返回，闭合括号里的括号也必须是成对且对应。如**([)]**因为第一个闭合的 ) 里的括号不成对且不对应，返回false
所以这个题我们可以考虑使用栈来存储，左括号压入栈，右括号和栈顶的左括号匹配，对不上返回fasle，匹配结束判断栈是否为空（因为括号成对出现）

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 1) return false;
        Stack<Character> stack = new Stack<>();
        char c = 0;
        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{')
                // 左括号入栈
                stack.push(c);
            else {
                // 右括号判断栈顶的括号是否匹配
                if (stack.empty())
                    return false;
                if (c == ')' && stack.pop() != '(')
                    return false;
                if (c == ']' && stack.pop() != '[')
                    return false;
                if (c == '}' && stack.pop() != '{')
                    return false;
            }
        }
        return stack.empty();
    }
}

第二种解法

括号是像洋葱那样一层一层的包裹起来的（如果你愿意一层一层的剥开我的心），那么最中间的绝对是一对且紧挨这的，如 **({[]})**，所以我们可以利用这个特性进行替换，最后只要长度大于0就说明是单个括号存在的

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 1) return false;
        while (s.indexOf("()") != -1 || s.indexOf("[]") != -1
            || s.indexOf("{}") != -1) {
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        }
        return s.trim().length() == 0;
    }
}