LeetCode 20：有效的括号 Valid Parentheses

TesterHome 发布于2019-08-19 10:17 / 2622人阅读

摘要：给定一个只包括，，，，，的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。注意空字符串可被认为是有效字符串。

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

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 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

欢迎关注微信公.众号：爱写Bug

云服务器 GPU云服务器 Parentheses LeetCode python中的括号 html向下的括号

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75768.html

[Leetcode] Longest Valid Parentheses 最长有效括号对

摘要：假设是从下标开始到字符串结尾最长括号对长度，是字符串下标为的括号。如果所有符号都是，说明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

everfight 2019-08-14 16:11 评论0 收藏0
[Leetcode] Valid Parentheses 验证有效括号对

摘要：如栈中是，来一个变成，再来一个，变成。注意栈在或者操作之前要验证非空，否则会抛出。代码最后要判断栈的大小，如果循环结束后栈内还有元素，说明也是无效的代码 Valid Parentheses Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is...

zhkai 2019-08-14 16:11 评论0 收藏0
LeetCode 之 JavaScript 解答第20题 —— 有效的括号（Valid Parent

摘要：小鹿题目给定一个只包括，，，，，的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。注意空字符串可被认为是有效字符串。除去这两种情况都不是符合条件的。 Time：2019/4/11Title: Valid ParenthesesDifficulty: EasyAuthor: 小鹿题目：Valid Parentheses Given a string c...

novo 2019-08-23 16:54 评论0 收藏0
Leetcode20 - Valid Parentheses

摘要：第一反应是用栈，然后将左括号入栈，右括号出栈，遍历结束后看看是不是栈空了。但是由于频繁的函数调用，导致时间效率不如第一个。但是第一个的方法更容易出错。 Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. The br...

iOS122 2019-08-14 12:10 评论0 收藏0
[leetcode]Longest Valid Parentheses

摘要：在问题中，我们可以用来检验括号对，也可以通过来检验。遇到就加一，遇到就减一。找到一对括号就在最终结果上加。我们用来表示当前位置的最长括号。括号之间的关系有两种，包含和相离。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

qujian 2019-08-14 16:53 评论0 收藏0