括号字符串的有效性

[编程题]括号字符串的有效性

热度指数：7333 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串str，判断是不是整体有效的括号字符串(整体有效：即存在一种括号匹配方案，使每个括号字符均能找到对应的反向括号，且字符串中不包含非括号字符)。

数据范围： $0 < len(str) \le 10^{5} \$

输入描述:

输入包含一行，代表str。

输出描述:

输出一行，如果str是整体有效的括号字符串，请输出“YES”，否则输出“NO”。

示例1

输入

(())

输出

YES

示例2

输入

()a()

输出

NO

说明

()a()中包含了 ‘a’，a不是括号字符

备注:

时间复杂度，额外空间复杂度

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAXLEN 100001

bool isValid(char *str);

int main(void) {
    char str[MAXLEN];
    scanf("%s", str);
    printf("%s\n", isValid(str) ? "YES" : "NO");
    return 0;
}

bool isValid(char *str) {
    int len = (int) strlen(str);
    int sum = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] != '(' && str[i] != ')')
            return false;
        sum += str[i] == '(' ? 1 : -1;
        if (sum < 0) return false;
    }
    return sum == 0;
}

发表于 2022-02-09 15:50:48 回复(0)