leetcode 20 Valid Parentheses

qiangdada 发布于2019-08-19 10:41 / 1393人阅读

摘要：判定是否有效的一句就是，字符必须严格有序。例如和是有效的，但是和就是无效的。对于前一半字符，我们对它们进行入栈操作。如果不匹配，即整个字符串无效。当整个字符串的遍历结束的时候，判断栈是否为空完全匹配。

题目详情

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.输入一个字符串s，这个字符串是由字符"(", ")", "{", "}", "[" 和 "]"组成的。我们需要判定这个字符串的格式是否有效。判定是否有效的一句就是，字符必须严格有序。例如"()" 和 "()[]{}"是有效的，但是"()"和"()[]{}"就是无效的。

想法

这道题目比较适合用栈作为存储中间结果的数据结构，因为字符应当是后进先出，方便我们进行判断。

对于前一半字符(eg.‘(’,"[","{")，我们对它们进行入栈操作。

如果遇到了后半字符，我们需要对栈顶元素取出，并判断栈顶字符和当前字符是否匹配。如果不匹配，即整个字符串无效。

当整个字符串的遍历结束的时候，判断栈是否为空（完全匹配）。

解法

        Stack save = new Stack();
        if(s.length() == 0)return true;
        
        for(char c : s.toCharArray()){
            if(c == "("){
                save.push(")");
            }else if (c == "["){
                save.push("]");
            }else if (c == "{"){
                save.push("}");
            }else if (save.isEmpty() || c != save.pop()){
                return false;
            }
        }
        
        return save.isEmpty();

云服务器 GPU云服务器 Parentheses Leetcod Valid LeetCode

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

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

LeetCode 20：有效的括号 Valid Parentheses

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

TesterHome 2019-08-19 10:17 评论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
[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] 32. Longest Valid Parentheses

Problem Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: (()Output: 2Explanation: The longest valid pa...

Flink_China 2019-08-19 11:14 评论0 收藏0