首页 > 试题广场 >

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

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

(()())

输出

示例2

输入

())

输出

备注:

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

算法知识视频讲解

Java

牛客939725647号

用链表思路实现的，思路还是比较清晰的

import java.util.Scanner;

import java.util.ArrayList;

public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String str = in.nextLine();
System.out.println(new Main().get_max_length(str));
}
int get_max_length(String str){
ArrayList<point> list = new ArrayList<point>();
for(int i = 0; i < str.length(); i++){
char ch = str.charAt(i);
point p = new point(i, ch);
if(ch == ')'){
for(int j = i - 1; j > -1; j--){
if(list.get(j).isbracket())
break;
if(list.get(j).ismatched()){
p.cor_id = j;
list.get(j).cor_id = i;
break;
}
}
}
list.add(p);
}
int max_length = 0;
int start_id = str.length() + 1, end_id = 0;
for(int i = 0; i < str.length(); i++){
if(list.get(i).cor_id == -1){
end_id = i;
int length = end_id - start_id;
max_length = length > max_length ? length : max_length;
start_id = str.length() + 1;
end_id = 0;
}else{
if(start_id > str.length())
start_id = i;
if(list.get(i).cor_id == str.length() - 1){
end_id = str.length();
int length = end_id - start_id;
max_length = length > max_length ? length : max_length;
}
i = list.get(i).cor_id;
}
}
return max_length;
}
class point{
char symbol;
int id;
int cor_id = -1;
point(int id, char symbol){
this.id = id;
this.symbol = symbol;
}
boolean ismatched(){
return symbol == '(' && cor_id == -1;
}
boolean isbracket(){
return symbol != '(' && symbol != ')';
}
}
}

发表于 2020-05-30 11:44:49 回复(0)

offer之神降临吧

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    cin >> str;
    vector<int> dp(str.size(), 0);
    
    int Max = 0;
    for(int i = 1; i < str.size(); i++){
        if(str[i] == ')'){
            if(str[i-1] == '('){
                dp[i] = 2 + (i-2 >= 0 ? dp[i-2] : 0);
                Max = max(Max, dp[i]);
            }
            else if(dp[i-1] != 0 && i-dp[i-1]-1 >= 0 && str[i-dp[i-1]-1] == '('){
                dp[i] = 2 + dp[i-1] + (i-dp[i-1]-2 >= 0 ? dp[i-dp[i-1]-2] : 0);
                Max = max(Max, dp[i]);
            }
        }
    }
    cout << Max << endl;
    return 0;
}

发表于 2020-05-15 20:14:15 回复(0)

别搁那忽悠人了


	#include <iostream>
(720)#include <string>
#include <stack>
(850)#include <vector>
using namespace std;



	int main()
{
    string str;
    cin >> str;
    int n = str.length();
    int index = 0;
    int m = 0;
    vector<int> dp(n,0);
    
    for (int i = 0;i < n;i++){
        if (str[i] == ')'){
            index = i - dp[i - 1] - 1;
            
            if ((index >= 0)&&(str[index] == '(')){
                dp[i] = dp[i - 1] + 2 +(index > 0 ? dp[index - 1]:0);
            }
        }
        m = max(m,dp[i]);
       
    }
    cout << m << endl;
    return 0;
}

发表于 2020-05-15 19:05:48 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    int Max = 0;
    vector<int>dp(str.size(),0);
    for(int i = str.size()-2; i >= 0; i--) 
    {
        if(str[i] == '(') 
        {
            int j = i + 1 + dp[i+1];
            if(j < str.size() && str[j] == ')') 
            {
                dp[i] += dp[i+1] + 2;
                if(j+1 < str.size())
                    dp[i] += dp[j+1];
            }
            if(Max < dp[i]) 
                Max = dp[i];
        }
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-09-24 19:57:32 回复(0)

Java

pein531

动态规划，一般像这种子串或子数组的题目求最值，就把以i结尾时的答案作为动规的状态，dp[i]是以i位置的字符结尾时0~i子串中最长的有效括号长度。这里我们注意到，如果i位置为左括号，0~i的子串一定无效，最长有效括号长度为0，只有它是右括号时才去考虑增加这个长度。如果i位置是右括号，就在不越界的情况下检查一下i-dp[i-1]-1位置是不是与之配对的左括号：

如果是，那么dp[i]至少为dp[i-1]+2（又增加了一个左括号和一个右括号）；
如果不是，那dp[i]一定是0。

最后在不越界的情况下，再把dp[i - dp[i-1] - 2]的长度累加上就可以了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int[] dp = new int[str.length];
        int maxLen = 0;
        for(int i = 1; i < str.length; i++){
            if(str[i] == ')'){
                int prev = i - dp[i - 1] - 1;
                if(prev >= 0 && str[prev] == '(')
                    dp[i] = dp[i - 1] + 2 + (prev > 0? dp[prev - 1]: 0);
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        System.out.println(maxLen);
    }
}

发表于 2021-11-22 22:56:49 回复(0)

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)

duerduer冲啊

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(),0);//dp[i]代表区间为[0,i](i是字符串下标)的最长有效长度
        int ans = 0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') dp[i] = 0;//最后一位是'('，说明这个子串有效长度是0
            else if (i-1>=0&&s[i-1]=='(') //最后一位是")"，需要分情况讨论倒数第二位，这里倒数第二位是左括号
                dp[i] = 2+(i-2>=0?dp[i-2]:0);//字符串举例："xxxx()"
            else if(i-1>=0&&s[i-1]==')'){//倒数第二位是右括号
                int prev_index = i-dp[i-1]-1;//与最后右括号匹配的左括号的下标索引,举例：(xxxx),中间xxxx合法字符串的有效长度是dp[i-1]
                int prev_prev_index = i-dp[i-1]-2;//上面左括号匹配的左边子串下标，举例：()(xxxx)
                if(prev_index>=0&&s[prev_index]=='(')
                    dp[i] = dp[i-1]+2+(prev_prev_index>=0?dp[prev_prev_index]:0);//把上面举例的两种情况合并
            }
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};
int main(){
    string s;
    cin>>s;
    Solution so;
    cout<<so.longestValidParentheses(s)<<endl;
    return 0;
}

编辑于 2021-02-09 12:02:14 回复(0)

牛客982038135号

我的哪里有问题了？

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int length = str.length();

        int left = 0;
        int right = 0;
        int size = 0;

        for (int i = 0; i < length; i++) {
            if (str.charAt(i) == '(') {
                left ++;
            } else {
                right ++;
                if (right == left) {
                    size = Math.max(2 * left, size);
                } else if (right > left) {
                    left = 0;
                    right = 0;
                }
            }
        }

        System.out.println(size);
    }
}

编辑于 2024-01-08 13:34:50 回复(0)

Python 3

奋斗小虎

Python3

s = input()
stack = [-1]
length = 0
max_length = 0
for i in range(len(s)):
    if s[i] == '(':
        stack.append(i)
    else:
        stack.pop()
        if stack:
            length = i - stack[-1]
            max_length = max(length, max_length)
        else:
            stack.append(i)
print(max_length)

发表于 2022-06-21 22:46:39 回复(0)

瑶瑶135755

java：

力扣32

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s8=new Scanner(System.in);
        String s=s8.nextLine();
        LinkedList<Integer> s1=new LinkedList<>();
        s1.push(-1);
        int max=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==')'){
                s1.pop();
                if(s1.isEmpty()) s1.push(i);
                else max=Math.max(max,i-s1.peek());
            }
            else s1.push(i);
        }
        System.out.println(max);
    }
}

发表于 2021-05-17 18:55:40 回复(0)

Java

眼睛想旅行121

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main{
    public static int MaxLength(String str){
        if(str==null||str.equals("")){
            return 0;
        }
        char[] chas=str.toCharArray();
        int[] dp=new int[chas.length];
        int pre=0;
        int res=0;
        for(int i=1;i<chas.length;i++){
            if(chas[i]==')'){
                pre=i-dp[i-1]-1;
                if(pre>=0&&chas[pre]=='('){
                    dp[i]=dp[i-1]+2+(pre>0?dp[pre-1]:0);
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        System.out.print(MaxLength(str));
    }
}

发表于 2021-03-31 10:51:00 回复(0)

想交流的豹子很怕黑

参考博客：

算法：最长有效括号【字符串、动态规划】

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(maxLength(s));
    }

    private static int maxLength(String s){
        if(s==null||s.length()<=1){
            return 0;
        }
        char[] chars = s.toCharArray();
        int max=0;
        int[] dp=new int[chars.length];
        
        for(int i=1;i<chars.length;i++){
            if(chars[i]==')'){
                 if(i-dp[i-1]-1>=0&&chars[i-dp[i-1]-1]=='('){
                    dp[i]=dp[i-1]+2+(i-dp[i-1]-1>0?dp[i-dp[i-1]-2]:0);//这一句代码分为3大部分：
                    max=Math.max(max,dp[i]);
                }
            }
        }
        return max;
    }
}

发表于 2021-03-22 23:37:59 回复(0)

GGBond-001

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int MaxLength(string &s)
{
    int len = s.length();
    int i = 0;
    vector<int> dp(len,0);
    int max = -1;
    for(i = 0;i < len;i++)
    {
//1.若s[i]为'(' dp[i] = 0；
        if(s[i] == '(')
        {
            dp[i] = 0;
        }
        else //2.若s[i]为')'
        {
            //2.1 判断前一个字符是否为'('与')'成为一组
            if(i >= 1 && s[i-1] == '(')
            {
//2.1.1 判断前面是否为有效
                if(i-2 >= 0 && dp[i-2] != 0)
                    dp[i] = dp[i-2]+2;
                else
                    dp[i] = 2;
            }
//2.2 若前一个字符为')'，有以下情况
            if(i >= 1 && s[i-1] == ')')
            {
//2.2.1 可能是 (()) 亦或是 ()(())
                if((i-dp[i-1]-1) >= 0 && s[i-dp[i-1]-1] == '(')
                {
// ()(())
                    if((i-1-dp[i-1]-1) >= 0 && dp[i-1-dp[i-1]-1] != 0)
                    {
                        dp[i] = dp[i-1] + 2 + dp[i-1-dp[i-1]-1];
                    }
                    else // (())
                    {
                        dp[i] = dp[i-1]+2;
                    }

                }
            }

        }
//找最大
        if(dp[i] > max)
        {
            max = dp[i];
        }

    }

    return max;
}
int main()
{
    /*string s = "()(()))";
    string s1 = "(((()(()))";
    string s2 = "(((())())((()))";
    int max = MaxLength(s);
    int max1 = MaxLength(s1);
    int max2 = MaxLength(s2);
    cout << max << endl;
    cout << max1 << endl;
    cout << max2 << endl;*/

    string str;
    cin >> str;
    cout << MaxLength(str) << endl;

    return 0;
}

发表于 2020-09-02 10:02:29 回复(0)

yyaihh

#include<iostream>
#include<string>
using namespace std;
class Solution{
public:
    static int fun(string& s) {
        int left = 0, right = 0, res = 0;
		for (auto c : s) {
			if (c == '(') {
				++left;
			}
			else if (c == ')') {
                ++right;
                if(right == left){
                    if(left > res) res = left;
                }
                else if(right > left){
                    left = right = 0;
                }
			}
            else {//有'*'
				left = right = 0;
			}
		}
        left = right = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
			if (s[i] == ')') {
				++right;
			}
			else if (s[i] == '(') {
                ++left;
                if(right == left){
                    if(right > res) res = left;
                }
                else if(left > right){
                    left = right = 0;
                }
			}
            else {
				left = right = 0;
			}
		}
		return 2 * res;
	}
};

int main(){
    string s;
    while(cin >> s){
        cout << Solution::fun(s) << endl;
    }
    return 0;
}

编辑于 2020-04-15 13:59:44 回复(0)

檐上

有没有大佬看看我这个思路，到底要怎么改正。case=80.95%，

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()) {
            String s = sc.nextLine();
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            int ret = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    stack.push(i);
                }

                if (c == ')') {
                    int pre = stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        if (stack.peek() >= 0 &&
                                isValid(s.substring(stack.peek(), i + 1))) {
                            ret = Math.max(ret, i - stack.peek());
                        } else {
                            if (isValid(s.substring(pre, i + 1))) {
                                ret = Math.max(ret, i - pre + 1);
                            }

                        }
                    }
                }
            }
            System.out.println(ret);
        }
    }

    private static boolean isValid(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '(' && s.charAt(i) != ')') {
                return false;
            }
        }
        return true;
    }
}

发表于 2020-03-02 11:32:32 回复(1)