资讯专栏INFORMATION COLUMN

[LeetCode] Valid Parentheses

AlphaWallet / 2928人阅读

摘要:循环每个元素放入堆栈或比较是否和栈顶元素成对。循环结束后,若未抛出,且堆栈为空,说明所有都已一一对应。

Problem

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.

Note

建立堆栈stack。循环每个元素放入堆栈或比较是否和栈顶元素成对。
循环结束后,若未抛出false,且堆栈为空,说明所有parenthese都已一一对应。

Solution HashMap+Switch/case
public class Solution {
    public boolean isValid(String s) {
        Map map = new HashMap<>();
        map.put("(", ")");
        map.put("[", "]");
        map.put("{", "}");
        Stack stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            switch (ch) {
                case "{": case "[": case "(":
                    stack.push(ch);
                    break;
                case ")": case "}": case "]":
                    if (stack.isEmpty() || ch != map.get(stack.pop())) return false;
            }
        }
        return stack.isEmpty();
    }
}
if-else branches
public class Solution {
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    public boolean isValidParentheses(String s) {
        char[] str = s.toCharArray();
        if (str.length % 2 != 0) return false;
        Stack stack = new Stack<>();
        for (char ch: str) {
            if (ch == "(" || ch == "[" || ch == "{") {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char top = stack.pop();
                    if ((ch == ")" && top != "(") || (ch == "]" && top != "[") || (ch == "}" && top != "{")) {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}

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

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

相关文章

  • [leetcode]Longest Valid Parentheses

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

    qujian 评论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 评论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 评论0 收藏0
  • [Leetcode] Valid Parentheses 验证有效括号对

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

    zhkai 评论0 收藏0
  • leetcode32 Longest Valid Parentheses 最长括号组的长度

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

    happyhuangjinjin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<