描述

难度：简单

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

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

思路

这种字符串类的题目，基本上99%都是要借助辅助栈、HashMap、list 来解决的。

有效括号，题目说：

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

同时符合这两个条件才能是有效括号，上面的示例4 就是不满足条件2。

• 方法一

既然要求顺序一致，那可以尝试使用栈来解决：

• 首先就是要循环遍历这个字符

   for (char c : s.toCharArray()) {
  

• 遇到左括号类型（{[(），我就把对应的右括号（}])）入栈。

if (c == '(') { //入栈 stack.push(')'); }

- 遇到右括号类型，我就**把栈顶弹出来**，如果当前位置和弹出来的括号是相同的，那就说明这一对是合法的，然后继续循环。

这里还有一个注意点，就是要判断空栈，如果是空栈，表示上一步都是没有入栈，出现的都是右括号类型，右括号开头的肯定就不是有效括号了，直接返回。

```java
if (stack.empty() || c != stack.pop()) {
	return false;
}

• 最后就是判断这个栈是否为空，如果为空，表示括号都匹配完毕，否则就是存在有左括号类型，没有机会出栈和 c 比较。

题解

public class 有效的括号20 {
    public static void main(String[] args) {
//        简单理解就是左边出现了 {，右边一定要是 }
//        String s = "()[]{}";
//        String s ="([)]";
//        String s = "((";
//        String s ="({{[]}})";
//        String s ="((";
        String s = "))";
        System.out.println(isValid(s));
    }


    /**
     * O(n) 复杂度
     *
     * @param s
     * @return
     */
    static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                //入栈
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
                // ]、}、) 进入这个判断
            } else if (stack.empty() || c != stack.pop()) {
                return false;
            }
        }
        //如果栈有剩下，可以理解为表示基数或者[[[[(((这种情况
        if (!stack.empty()){
            return false;
        }
        return true;
    }
}