力扣-20-有效的括号

有效的括号

Tags

Companies

---

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

知识点补充：

java中的栈（Stack）

1. 栈（Stack）是一种后进先出(先进后出)的数据结构。
2. 队列（Queue）是先进先出的数据结构。
3. LIFO：最后进栈的元素一定最早出栈。只需要把队列的一端封死即可。
4. 栈的基本操作
   1. 压栈：将元素存储到栈中 push（）；
   2. 弹栈：将元素从栈中拿出 pop（）；
   3. 取栈顶元素但不弹出 ： peek（）；可以拿来做对比。
   4. 判断栈是否为空 ： isEmpty（）；
   5. 返回对象在栈中的位置，以1为基数 search（obj）

思路：

1. 见到括号问题首先想到的是使用栈来解决问题。
2. 认真读题目可以发现要求
   1. 左括号必须用相同类型的右括号闭合
   2. 左括号必须以正确的顺序闭合。
   3. 每个右括号都有一个对应的相同类型的左括号。
   4. 不难看出这样就排除了顺序混乱的问题。这样我们解决问题就简单多了。
   5. 也就是无论多负责只能出现下面这种情况：((({{{[[[[[((((({{{{[[[]]]}}}})))))]]]]]}}})))

答案：

class Solution {
    public boolean isValid(String s) {
        //排除如果s为空数组和s=“”的情况
        if (s == "" || s == null) {
            return false;
        }
        Stack<Character> left = new Stack<>();
        // for (char c : s.toCharArray()) {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // }
            if (c == '(' || c == '[' || c == '{') {
                left.push(c);
            } else {
                // 如果是右括号
                if (!left.isEmpty() && leftof(c) == left.peek()) {
                    left.pop();
                } else {
                    // 和最近的括号不匹配就返回false
                    return false;
                }
            }
        }
        // 是否所有左括号都被匹配了
        return left.isEmpty();
    }
    public char leftof(char c) {
        if (c == ')') {
            return '(';
        } else if (c == ']')
            return '[';
        else {
            return '{';
        }
    }
}