专栏首页木又AI帮【leetcode刷题】T86-有效的括号字符串

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

【题目】

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

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

输入: "()"
输出: 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 == ;
    }
};

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

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

原始发表时间:2019-06-09

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    木又AI帮
  • 【leetcode刷题】T193-各位相加

    https://leetcode-cn.com/problems/add-digits/

    木又AI帮
  • 【leetcode刷题】T45-丑数

    Write a program to check whether a given number is an ugly number.

    木又AI帮
  • 二分查找

    /* 功能:二分查找 日期:2013-05-16 */ #include <stdio.h> #include <stdlib.h> #includ...

    汐楓
  • 我的2016年书单

    相对于电子书,我更喜欢纸质版的书籍。我喜欢在拿到新书时记录购买时间、地点、开始阅读的时间、第一次看完的时间,算是一种学习的记录。过去的2016年一共阅读过15本...

    JavaQ
  • Java后端工程师必备书单(含大后端方向相关书籍)

    作者黄小斜,斜杠青年,某985硕士,阿里研发工程师,于2018 年秋招拿到 BAT 头条、网易、滴滴等 8 个大厂 offer

    黄小斜
  • 服务端接口自动化测试工具大全及适配环境解析

    在互联网时代,服务端测试已经成为一个重要的产品保障手段,各对此公司实施的方法和技术也不同,本文我们就来讨论一下。 互联网服务端接口自动化是各个公司都需要一部分业...

    CSDN技术头条
  • 论接口自动化测试方法

    每当我们谈起自动化测试时,第一反应是UI自动化测试;而具有一些经验的测试人员,则会非常慎重的对待UI自动化,他们会更加倾向于接口自动化测试。究其缘由,主要是因为...

    上帝De助手
  • 从零开始的Python学习Episode

    注意:输入的信息会被认为是字符串,如果要输入数字进行运算要先把输入的信息进行强制类型转换,如result = int(num) - 1

    py3study
  • Vue这些修饰符帮我节省20%的开发时间

    为了方便大家写代码,vue.js给大家提供了很多方便的修饰符,比如我们经常用到的取消冒泡,阻止默认事件等等~

    winty

扫码关注云+社区

领取腾讯云代金券