LeetCode 20：有效的括号 Valid Parentheses

爱写bug

发布于 2019-08-05 17:09:47

4430

发布于 2019-08-05 17:09:47

文章被收录于专栏：爱写Bug

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

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

有效字符串需满足：

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

注意空字符串可被认为是有效字符串。

Note that an empty string is also considered valid.

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

解题思路：

很简单的题，将字符串每个字符压入栈，简单判断即可。如：

输入: "{[]}"
初始栈为空，'{' 入栈
下一个字符
栈顶元素 '{'与 '[' 不匹配，'[' 入栈
下一个字符
栈顶元素 '['与 ']' 匹配，'[' 出栈
下一个字符
栈顶元素 '{'与 '}' 匹配，'}' 出栈
结束，栈为空，返回 True

关键在于判断字符是否匹配，匹配的标准是相反的括号字符，并非相同字符。可以用 switch 判断三种括号字符，或者三个 if 语句，再或者可以用散列表映射括号关系。

Java：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();//初始化栈
        for (char b : s.toCharArray()) {
            switch (b) {
                case '(': {
                    stack.push(')');
                    break;
                }
                case '{': {
                    stack.push('}');
                    break;
                }
                case '[': {
                    stack.push(']');
                    break;
                }
                default: {//不匹配的情况返回false
                    if (stack.isEmpty() || stack.pop() != b) {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();//栈为空则证明全部匹配，返回true，否则返回false
    }
}

Python:

注：python中没有 switch...case... 语句，官方让用 if 判断代替...

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '[':
                stack.append(']')
            elif c == '(':
                stack.append(')')
            elif c == '{':
                stack.append('}')
            elif len(stack) == 0 or stack.pop() != c:
                return False
        return len(stack) == 0

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自爱写Bug 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度