美文网首页
最长有效括号(复习重点)

最长有效括号(复习重点)

作者: 环宇飞杨 | 来源:发表于2020-04-19 22:28 被阅读0次

题目

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解题思路

精疲力尽....连续10个小时,最后还是抄了题解,找转移方程真是太费劲了,自己的解法总是遇到无穷无尽的边界判断,脑子要炸了。

代码

class Solution {
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        int dp[] = new int [s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')'){
                if (s.charAt(i - 1) == '('){ //上一个括号可以和当前形成组合
                    dp[i] = ( i >= 2 ? dp[i - 2] : 0) +2;
                }else if(i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '('){ //排除掉已经计算过的括号后,再判断前一个括号是否可以和当前形成组合,dp[i - 1]代表上一步中已经得知的有效括号长度,减去这个长度后就可方便的得到尚未匹配的那个括号。
                    dp[i] = dp[i - 1] + ((i -2 - dp[i - 1]) >= 0 ? dp[i -2 - dp[i - 1]]:0)  + 2 ;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
}

相关文章

  • 最长有效括号(复习重点)

    题目 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(...

  • 最长有效括号

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/long...

  • 最长有效括号

    //给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。//输入:s = ...

  • 最长有效括号

    难点在于()()如何匹配前面的连续(),还有(())如何处理 举例:s[i-2]==")" ()([)]=>dp[...

  • 最长有效括号

    32. 最长有效括号 题目: 给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串...

  • LeetCode-32-最长有效括号

    LeetCode-32-最长有效括号 题目 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的...

  • LeeCode刷题笔记4:最长有效括号

    @[TOC](最长有效括号) 题目描述 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串...

  • 32. 最长有效括号

    32. 最长有效括号 视频讲解挺好的

  • leetcode 32 最长有效括号

    32. 最长有效括号 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1...

  • 最长的有效括号

    题目描述:给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度. 示例:输入: ")(...

网友评论

      本文标题:最长有效括号(复习重点)

      本文链接:https://www.haomeiwen.com/subject/xjlwbhtx.html