首页 > 试题广场 >

有效的括号字符串

[编程题]有效的括号字符串
  • 热度指数：1835 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  5. 一个空字符串也被视为有效字符串。
示例1

输入

"()"

输出

true
示例2

输入

"(*)"

输出

true
示例3

输入

"(*))"

输出

true

备注:
字符串大小将在 [1，100] 范围内。

算法知识视频讲解
添加回答
Python
卡瓦夏日头像 卡瓦夏日 
class Solution:
    def checkValidString(self , s ):
        res=[]
        for i in s:
            if i=='('&nbs***bsp;i=='*':
                res.append(i)
            else:
                j=1
                while j<=len(res) and res[-j]!='(':
                    j+=1
                if j<=len(res):
                    del res[-j]
                elif len(res)!=0:
                    res.pop()
                elif len(res)==0:
                    return False
        r=[]#stack for *
        i=0
        for i in range(len(res)-1,-1,-1):
            if res[i]=="*":
                r.append(res[i])
            else:
                if len(r)>0 and r[-1]=="*":
                    r.pop()

                else:
                    return False
        if '(' not in r:
            return True

发表于 2021-04-19 21:11:33 回复(0)
Python
牛客198789950号头像 牛客198789950号
class Solution:
    def checkValidString(self , s ):
        # write code here
        T=['s']
        for i in s:
            if i=='(' or i=='*':
                T.append(i)
            elif i==')':
                kk=len(T)-1
                while T[kk]=='*':
                    kk-=1
                if kk==0:
                    T.pop()
                else: T.pop(kk)
            if len(T)<1: break
        if len(T)<1: return False
        if T.count('(') >T.count('*')+1 or T[-1]=='(': return False
        else: return True
发表于 2021-03-24 22:49:13 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 测试开发工程师 深圳虾皮信息科技有限公司 大数据开发工程师 Java工程师
上传者：小小
难度：
2条回答 5661浏览

热门推荐

通过挑战的用户

相关试题

有效的括号字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号