题目

代码分析

可以使用栈，暴力的方式来解题
最好使用动态规划，dp[i]表示以str[i]为结尾的最长的有效括号，状态转移方程如下
case 1: .........()

如果当前是(,上一个位置是)

case 2: .........))

dp[i]=dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);

注意三元运算符的括号

代码总结

/*
    枚举法判断有效的括号数量
     */
    public static int longestValidParentheses3(String s)
    {
        int res=0;
        for(int i=0;i<s.length();i++)
            for(int j=i+2;j<s.length()+1;j+=2)
            {
                if(isValid(s.substring(i,j)))
                {
                   System.out.println(i+" "+j);
                   res=Math.max(res,j-i);
                   System.out.println(res);
                }
            }
        return res;
    }
    /*
    括号是否合法
    )()())
     */
    public static boolean isValid(String s)
    {
        char[] chas = s.toCharArray();
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<chas.length;i++)
        {
            if(chas[i]=='(')
            {
                stack.push('(');
            }
            else if(chas[i]==')'&&!stack.isEmpty()&&stack.peek()=='(')
            {
                stack.pop();
            }else
            {
                return false;
            }
        }
        return stack.isEmpty();
    }

 public int longestValidParentheses(String s) {
        char[] chas=s.toCharArray();
        int[] dp=new int[s.length()];
        int max=0;
        for(int i=1;i<s.length();i++)
        {
            if(chas[i]==')')
            {
                if(chas[i-1]=='(')
                {
                     dp[i]=(i-2>=0?dp[i-2]:0)+2;
                }else if(i-dp[i-1]-1>=0&&chas[i-dp[i-1]-1]=='(')
                {
                    dp[i]=dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);
                }
            }
            max=Math.max(max,dp[i]);
        }

        return max;
    }

学习情况

1次