[Leetcode] Valid Parentheses 验证有效括号对

zhkai 发布于2019-08-14 16:11 / 1741人阅读

摘要：如栈中是，来一个变成，再来一个，变成。注意栈在或者操作之前要验证非空，否则会抛出。代码最后要判断栈的大小，如果循环结束后栈内还有元素，说明也是无效的代码

Valid Parentheses

Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

栈法 复杂度

时间 O(N) 空间 O(N)

思路

栈最典型的应用就是验证配对情况，作为有效的括号，有一个右括号就必定有一个左括号在前面，所以我们可以将左括号都push进栈中，遇到右括号的时候再pop来消掉。这里不用担心连续不同种类左括号的问题，因为有效的括号对最终还是会有紧邻的括号对。如栈中是({[，来一个]变成({，再来一个}，变成(。

注意

栈在peek或者pop操作之前要验证非空，否则会抛出StackEmptyException。

代码最后要判断栈的大小，如果循环结束后栈内还有元素，说明也是无效的

代码

public class Solution {
    public boolean isValid(String s) {
        Map map = new HashMap();
        map.put("(",")");
        map.put("[","]");
        map.put("{","}");
        Stack stk = new Stack();
        for(int i = 0; i < s.length(); i++){
            Character c = s.charAt(i);
            switch(c){
                case "(": case "[": case "{":
                    stk.push(c);
                    break;
                case ")": case "]": case "}":
                    if(stk.isEmpty() || c != map.get(stk.pop())){
                        return false;
                    }
            }
        }
        return stk.isEmpty();
    }
}

2018/2

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if c == "(" or c == "{" or c == "[":
                stack.append(c)
            elif not stack:
                return False
            elif c == ")" and stack.pop() != "(":
                return False
            elif c == "}" and stack.pop() != "{":
                return False
            elif c == "]" and stack.pop() != "[":
                return False
        return not stack

云服务器 GPU云服务器有效性验证 Parentheses 无法验证对路径无法验证对路径的访问

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

转载请注明本文地址：https://www.ucloud.cn/yun/66166.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 20：有效的括号 Valid Parentheses

摘要：给定一个只包括，，，，，的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。注意空字符串可被认为是有效字符串。给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。 Given a string containing just the characters (, ), {, }, [ and ], determine if the inpu...

TesterHome 2019-08-19 10:17 评论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
leetcode32 Longest Valid Parentheses 最长括号组的长度

摘要：题目要求原题地址一个括号序列，求出其中成对括号的最大长度思路一使用堆栈这题可以参考我的另一篇博客这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。在这里需要先遍历一遍字符串，再遍历一下非空的堆栈。题目要求原题地址：https://leetcode.com/problems... Given a string containing just the c...

happyhuangjinjin 2019-08-14 18:13 评论0 收藏0
【LeetCode Easy】020 Valid Parentheses

摘要：三种括号匹配问题，判断参数字符串是否满足匹配要求如空串为括号匹配问题是栈的典型应用，遇到左括号，入栈，遇到右括号，看栈顶是否是相应的左括号，若不是，则时间复杂度代码如下思想是一样的，不过没有用栈这个数据结构，而是用了一个定长数组，对于参数的 Easy 020 Valid Parentheses Description: () [] {}三种括号匹配问题，判断参数字符串是否满足匹配要求如...

Yangyang 2019-08-16 17:09 评论0 收藏0