首页 > 试题广场 >

合法的括号字符串

[编程题]合法的括号字符串
  • 热度指数：12274 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
5.空字符串也视为合法的括号字符串

数据范围:

示例1

输入

"()()"

输出

true
示例2

输入

"((*)"

输出

true
示例3

输入

"(*)"

输出

true
示例4

输入

"(((*)"

输出

false
算法知识视频讲解
添加回答
Go
牛客59748629号头像 牛客59748629号
func isValidString(s string) bool {
    var stack []rune = make([]rune, 0)
    for i := range s {
        switch s[i] {
        case '(':
            stack = append(stack, '(')
        case '*':
            stack = append(stack, '*')
        case ')':
            if len(stack) < 1 {
                return false
            }
            var index int
            for index = len(stack) - 1; index >= 0; index-- {
                if stack[index] == '(' { //不可能遇到 )
                    break
                }
            }
            if index >= 0 { //栈中有 (
                stack[index] = '*'
            }
            stack = stack[:len(stack)-1]

        }
    }
    if len(stack) < 0 {
        return true
    }
    //如果stack不为空，则剩余的一定是 ( *
    i := len(stack) - 1
    for i >= 0 {
        if stack[i] == '(' {
            if i+1 < len(stack) && stack[i+1] == '*' {
                tmp := stack[0:i]
                tmp = append(tmp, stack[i+2:]...)
                stack = tmp
                //i--
            } else {
                return false
            }
        }
        i--
    }
    return true
}

发表于 2024-04-24 11:25:59 回复(0)
提交观点

问题信息

贪心 动态规划 字符串 栈
上传者：牛客301499号
难度：
2条回答 6299浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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