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

【leetcode刷题】T86-有效的括号字符串

作者头像
木又AI帮
修改2019-07-18 10:23:02
4610
修改2019-07-18 10:23:02
举报
文章被收录于专栏:木又AI帮木又AI帮

【题目】

给定只包含( ,) 和 *三种字符的字符串,写一个函数来检验是否为有效字符串。有效字符串规则如下:

  • 任何左括号 ( 必须有相应的右括号 )。
  • 任何右括号 ) 必须有相应的左括号 ( 。
  • 左括号 ( 必须在对应的右括号之前 )。
  • *可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
  • 一个空字符串也被视为有效字符串。
示例 :

输入: "()"
输出: True
示例 :

输入: "(*)"
输出: True
示例 :

输入: "(*))"
输出: True

注意:

字符串大小将在 [1,100] 范围内。

【思路】

我们可以把'*'当做'('或者')',相当于'('个数不确定。

用low、high分别存储剩余的'('的最少个数(最小为0)和最多个数,因此,low把'*'和')'都视为')',能减则减(大于0的前提下),high把'*'视为'(',遇到'*'自增,遇到')'自减。最后判断low是否为0,返回结果。

具体来说,遍历字符串,当遇到'(',low和high都自增;当遇到')',low>0时才自减,high自减,只要high<0,说明当前右括号数太多,返回False;当遇到'*',low>0时自减,high自增。最后,返回low==0。

【代码】

python版本

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == '':
            return True
        # 最少'('个数low,最多'('个数high
        low = 
        high = 
        for si in s:
            if si == '(':
                low += 
                high += 
            elif si == ')':
                if low > :
                    low -= 
                high -= 
                if high < :
                    return False
            else:
                if low > :
                    low -= 
                high += 
        return low == 

C++版本

class Solution {
public:
    bool checkValidString(string s) {
        // 最多左括号个数high,最少左括号个数low
        int low=, high=;
        char si;
        for(int i=; i<s.size(); i++){
            si = s[i];
            if(si == '('){
                low++;
                high++;
            }else{
                if(si == ')'){
                    if(low > )
                        low--;
                    high--;
                    if(high < )
                        return false;
                }else{
                    if(low > )
                        low--;
                    high++;
                }
            }
        }
        return low == ;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-06-09,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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