首页 > 试题广场 >

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

[编程题]括号字符串的最长有效长度
  • 热度指数：5733 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个括号字符串str，返回最长的能够完全正确匹配括号字符字串的长度。

输入描述:
输出一行字符串，代表str。


输出描述:
输出一个整数，代表括号字符串的最长有效长度。
示例1

输入

(()())

输出

6
示例2

输入

())

输出

2

备注:
时间复杂度，额外空间复杂度。
算法知识视频讲解
添加回答
Java
pein531头像 pein531
动态规划，一般像这种子串或子数组的题目求最值，就把以i结尾时的答案作为动规的状态，dp[i]是以i位置的字符结尾时0~i子串中最长的有效括号长度。这里我们注意到，如果i位置为左括号，0~i的子串一定无效，最长有效括号长度为0，只有它是右括号时才去考虑增加这个长度。如果i位置是右括号，就在不越界的情况下检查一下i-dp[i-1]-1位置是不是与之配对的左括号：
  1. 如果是，那么dp[i]至少为dp[i-1]+2（又增加了一个左括号和一个右括号）；
  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)
Java
眼睛想旅行121头像 眼睛想旅行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)
Java
牛客939725647号头像 牛客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)
提交观点

问题信息

上传者：小小
难度：
3条回答 8995浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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