专栏首页木又AI帮【leetcode刷题】20T14-有效的括号

【leetcode刷题】20T14-有效的括号


木又同学2020年第14篇解题报告

leetcode第20题:有效的括号

https://leetcode-cn.com/problems/valid-parentheses/


【题目】

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

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

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

【思路】

开心~又一次写完代码,一跑,全部通过

本题是栈的典型应用。遍历字符串,如果遇到'{'、'['、'}'这三个字符,则压栈;否则,判断栈是否为空,同时字符与栈顶元素是否对应,若任何一个条件不满足,则返回False。循环结束后,判断栈是否为空,如为空,则返回True。

【代码】

python版本

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # 奇数个,肯定不行
        if len(s) % 2 != 0:
            return False
        # 空字符串,返回True
        if s == '':
            return True

        d = {')': '(', ']': '[', '}': '{'}
        # 使用栈来存储
        stack = []
        for si in s:
            # 压栈
            if si in '([{':
                stack.append(si)
            # 弹栈
            else:
                if len(stack) == 0 or d[si] != stack[-1]:
                    return False
                stack.pop()
        return len(stack) == 0

C++版本

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0)
            return false;
        stack<char> res;
        bool flag = true;
        for (auto si: s) {
            if (si == '(' || si == '[' || si == '{') {
                res.push(si);
            } else {
                // 栈是否为空
                if (res.size() == 0) {
                    flag = false;
                    break;
                }
                // 元素是否对应
                if ((res.top() == '(' && si == ')') || (res.top() == '[' && si == ']') || (res.top() == '{' && si == '}')) {
                    res.pop();
                } else {
                    flag = false;
                    break;
                }
            }
        }
        return flag && res.size() == 0;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T116-二叉树的锯齿形层次遍历

    https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

    木又AI帮
  • 【leetcode刷题】T39-字符串中的第一个唯一字符

    Given a string, find the first non-repeating character in it and return it's ind...

    木又AI帮
  • 【leetcode刷题】T89-计数二进制子串

    给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

    木又AI帮
  • Leetcode【227、468、848、1081】

    这道题是实现一个基本计算器,即给一个只包括 +、-、*、/、数字和空格的字符串,计算结果。

    echobingo
  • python自学第三节课(笔记)

    被缩进的内容(print()函数)和if条件语句组成了一个代码块(一个整体),成为了if条件下的内部命令。

    小老鼠
  • Android网络之HttpUrlConnection和Socket关系解析

    多年以前Android的网络请求只有Apache开源的HttpClient和JDK的HttpUrlConnection,近几年随着OkHttp的流行Androi...

    静默加载
  • 编写优雅代码的最佳实践

    Robert Martin曾说过"在代码阅读中说脏话的频率是衡量代码质量额唯一标准"。同时,代码的写法应当使别人理解它所需的时间最小化,也就是说我们写的代码是给...

    木可大大
  • ISO C forbids comparison between pointer and integer [-fpermissive]

    异常:ISO C forbids comparison between pointer and integer [-fpermissive] 意思是:指针和...

    公众号-不为谁写的歌
  • 编写优雅代码的最佳实践

    Robert Martin曾说过"在代码阅读中说脏话的频率是衡量代码质量额唯一标准"。同时,代码的写法应当使别人理解它所需的时间最小化,也就是说我们写的代码是给...

    木可大大
  • leetcode 20 Valid Parentheses 括号匹配

    Given a string containing just the characters '(', ')', '{', '}', '[' and']', d...

    流川疯

扫码关注云+社区

领取腾讯云代金券