栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

最长有效括号

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

最长有效括号

最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

问题思路
  • 所用方法:动态规划。
  • 状态分析:将以该字符为结尾的最长有效括号子串的长度作为这个字符位置的状态。
  • 具体解决:如果这个字符为’(‘则一定为0,因为’(‘不能作为有效括号字串的末尾。如果这个字符为’)‘,那么就要看它的前一个字符,如果是’)‘,因为已经知道了前一个字符的状态(即对应的有效长度),那么减去这个长度后观察前面的是否能与当前的组成一对,如果是’)‘,那么不能组成,则当前字符状态为0,如果是’(',那么可以组成一对,这时它的状态为它前一位的状态加2,另外需要再观察是否和前面的能继续凑成有效字串,即加上新凑成字串的前一位的状态。
代码
package OneHundred;
import java.util.ArrayList;
import java.util.Stack;
public class Que16 {
    public int longestValidParentheses(String s) {
        int len=0;
        int[] dp=new int[s.length()];
        for(int i=0;i
            if(s.charAt(i)=='('){
                dp[i]=0;
            }else{
                if(i==0){
                    dp[i]=0;
                    continue;
                }
                if(s.charAt(i-1)=='('){
                    if(i>1){
                    dp[i]=dp[i-2]+2;}
                    else{dp[i]=2;}
                }else{
                    if((i-dp[i-1] - 1>=0)&&(s.charAt(i-dp[i-1] - 1)=='(')){
                        dp[i]=i-dp[i-1]-2>0?dp[i-1]+2+dp[i-dp[i-1]-2]:dp[i-1]+2;
                    }else{
                        dp[i]=0;
                    }
                }
            }
            if(dp[i]>len){
                len=dp[i];
            }
        }
        return len;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/940591.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号