括号字符串的最长有效长度

[编程题]括号字符串的最长有效长度

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

给定一个括号字符串str，返回最长的能够完全正确匹配括号字符字串的长度。

输入描述:

输出一行字符串，代表str。

输出描述:

输出一个整数，代表括号字符串的最长有效长度。

示例1

输入

(()())

输出

示例2

输入

())

输出

备注:

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

算法知识视频讲解

helloxuanbao

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

#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define MAXLEN 100001

int main(void) {
    int len, *dp, pre, res = 0;
    char str[MAXLEN];
    scanf("%s", str);
    len = (int) strlen(str);
    dp = (int *) malloc(sizeof(int) * len);
    dp[0] = 0;
    for (int i = 1; i < len; i++) {
        if (str[i] == '(') {
            dp[i] = 0;
            continue;
        }
        pre = i - dp[i - 1] - 1;
        if (pre >= 0 && str[pre] == '(') {
            dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
        }
        res = MAX(res, dp[i]);
    }
    printf("%d\n", res);
    free(dp);
    return 0;
}

发表于 2022-02-09 16:23:02 回复(0)