【LeetCode】2. Valid Parentheses·有效的括号

题目描述

英文版描述

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

英文版地址

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

中文版描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([)]"

输出：false

示例 5：

输入：s = "{[]}"

输出：true

Constraints·提示：

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

中文版地址

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

解题思路

因为需要按顺序闭合，即最先出现的右括号需要能与离他最近的左括号配成对，且到最后无剩余的左括号或者右括号，所以考虑可以利用栈结构先进后出的特性，将未配对的括号压入栈中，每读取一个新的括号，就查看其与栈顶元素是否匹配，匹配则弹出栈顶元素，不匹配则将当前元素入栈，然后继续下一个，直到没有新元素了，如果此时栈为空，则该字符串有效，反之无效。

解题方法

俺这版

    public static boolean isValid(String s) {
        Stack stack = new Stack();
//        stack.push(s.charAt(0));
        // 分别获取各个括号的ASCII码值
        int parenthesesLeft = Integer.valueOf('(');
        int parenthesesRight = Integer.valueOf(')');
        int middleBracketLeft = Integer.valueOf('[');
        int middleBracketRight = Integer.valueOf(']');
        int curlyBracketLeft = Integer.valueOf('{');
        int curlyBracketRight = Integer.valueOf('}');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int value = Integer.valueOf(c);
            // 获取栈顶元素的ASCII码
            char peek;
            int peekValue;
            // 左半边的直接入栈，右半边的查看与栈顶元素是否匹配
            if (value == parenthesesLeft || value == middleBracketLeft || value == curlyBracketLeft) {
                stack.push(c);
                continue;
            } else if (value == parenthesesRight || value == middleBracketRight || value == curlyBracketRight) {
                if (stack.isEmpty()) {
                    return false;
                }
                peek = (char) stack.peek();
                peekValue = Integer.valueOf(peek);
                if (value == parenthesesRight) {
                    if (peekValue == parenthesesLeft) {
                        stack.pop();
                        continue;
                    }
                } else if (value == middleBracketRight) {
                    if (peekValue == middleBracketLeft) {
                        stack.pop();
                        continue;
                    }
                } else if (value == curlyBracketRight) {
                    if (peekValue == curlyBracketLeft) {
                        stack.pop();
                        continue;
                    }
                }
                return false;
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

官方版

public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {
   {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

欢迎有更好方法的同学评论区戳戳*〜（ゝ。∂）～～～