20. 有效的括号

题目地址(20. 有效的括号)

https://leetcode-cn.com/problems/valid-parentheses/

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

前置知识

公司

• 暂无

思路

先来分析一下 这里有三种不匹配的情况，

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。

1. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。

1. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

把这3点排除了就可以保证括号的正确匹配了

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
        public boolean isValid(String s) {
            Deque<Character> stack = new LinkedList<>();
            char temp ;
            for (int i = 0; i < s.length(); i++) {
                temp = s.charAt(i);
                //如果temp是左括号 就将对应的右括号添加到栈中
                if (temp == '(') {
                    stack.push(')');
                } else if (temp == '{') {
                    stack.push('}');
                } else if (temp == '[') {
                    stack.push(']');
                }else if (stack.isEmpty() || stack.peek() != temp) {
                    //进行到这个位置的话 只会出现右括号的情况 如果栈为空说明括号出现了多余的右括号
                    //如果栈顶的位置不=当前的右括号 说明括号不对应 比如 (}
                    return false;
                }else {
                    //到这个位置说明括号是对应的 这时将栈顶的括号弹出
                    stack.pop();
                }
            }
            //最后栈为空返回true 不为空说明有括号没匹配完即有多余的左括号
            return stack.isEmpty();
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=gvXSZ)
• 空间复杂度：#card=math&code=O%28n%29&id=rHMXK)