首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode刷题】T19-有效的括号

【leetcode刷题】T19-有效的括号

作者头像
木又AI帮
发布2019-07-17 10:03:28
3570
发布2019-07-17 10:03:28
举报
文章被收录于专栏:木又AI帮木又AI帮
今天分享leetcode第19篇文章,也是leetcode第20题—有效的括号(Valid Parentheses),地址是:https://leetcode.com/problems/valid-parentheses/从本题开始,将开始解决栈相关的问题。【英文题目】(学习英语的同时,更能理解题意哟~)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.Example :Input: "()"
Output: true
【中文题目】给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例:输入: "()"
输出: true
【思路】我们可以使用栈保留左括号,每遇到一个右括号,从栈中弹出一个左括号,并判断是否和右括号对应。【代码】python版本class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ls = []
        # 使用字典,节省代码,否则要分别判断括号对应关系
        d = {'}':'{', ')':'(', ']':'['}
        for si in s:
            if si in '([{':
                ls.append(si)
            else:
                # ls没有元素或者元素不匹配
                if len(ls) == 0 or d[si] != ls[-1]:
                    return False
                else:
                    ls.pop()
        return len(ls) == 0
C++版本class Solution {
public:
    bool isValid(string s) {
        stack<char> ls;
        map<char, char> d;
        // 使用字典,节省代码,否则要分别判断括号对应关系
        d['}'] = '{';
        d[')'] = '(';
        d[']'] = '[';
        for(char si:s){
            if(si == '{' or si == '(' or si == '[')
                ls.push(si);
            else{
                // ls没有元素或者元素不匹配
                if((ls.size() == 0) or (d[si] != ls.top()))
                    return false;
                // 弹出元素
                ls.pop();
            }  
        }
        return ls.size() == 0;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-03-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 木又AI帮 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档