leetcode 32. 最长有效括号

桃扇骨 2023-07-02 10:27 2阅读 0赞

思路：

动态规划 ，dp\[i\]表示以s\[i\]结尾的，最长的子串长度

很明显,当s\[i\]=='('时，不能构成完整子串，dp\[i\]=0,

当s\[i\]==')'时，若s\[i-1\]==‘（’，则dp\[i\]=dp\[i-2\]+2

当s\[i-1\]==')'时，则需要向前找，看是否有s\[j\]==‘（’ ，因为要构成子串，所以只需看dp\[i-1\]构成的子串的开始位置，往前找一个就行。若s\[i-dp\[i-1\]-1\]=='(' 则 dp\[i\]=dp\[i-1\]+dp\[i-dp\[i-1\]-2\]+2

代码：

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n=s.size();
            int dp[n+7];
            int M=0;
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++)
            {
                if(s[i-1]=='(')
                {
                    dp[i]=0;
                }
                else
                {
                    if(i>=2&&s[i-2]=='(')
                    {
                        dp[i]=dp[i-2]+2;
                    }
                    else if(i>=(dp[i-1]+2)&&s[i-dp[i-1]-2]=='(')
                    {
                        dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                    }
                    else
                    {
                        dp[i]=0;
                    }
                }
                M=max(M,dp[i]);
            }
            return M;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 116 阅读

相关 leetcode 32. 最长有效括号

思路：动态规划，dp\[i\]表示以s\[i\]结尾的，最长的子串长度很明显,当s\[i\]=='('时，不能构成完整子串，dp\[i\]=0, 当s\[i\]==

桃扇骨/ 2023年07月02日 10:27/ 0 赞/ 3 阅读

相关 leetcode32 最长有效括号

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

た入场券/ 2023年06月18日 05:54/ 0 赞/ 13 阅读

相关 32. 最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号

我会带着你远行/ 2023年02月22日 13:55/ 0 赞/ 6 阅读

相关 Leetcode 最长有效括号

利用括号匹配的算法以及栈，就可以算出匹配序列，然后利用两个变量记录有效括号的起始值与结束值，就可以得到最长有效括号。 include<stdio.h> inc

左手的ㄟ右手/ 2023年02月22日 13:52/ 0 赞/ 2 阅读

相关 32. 最长有效括号

[https://leetcode-cn.com/problems/longest-valid-parentheses/][https_leetcode-cn.com_prob

今天药忘吃喽~/ 2022年09月10日 11:27/ 0 赞/ 147 阅读

相关 LeetCode32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串

系统管理员/ 2022年09月08日 00:12/ 0 赞/ 139 阅读

相关 leetcode 32. Longest Valid Parentheses 最长有效括号长度

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longes

旧城等待，/ 2022年06月09日 09:41/ 0 赞/ 168 阅读

相关 LeetCode 32. Longest Valid Parentheses (最长有效括号)

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

╰+哭是因爲堅強的太久メ/ 2022年05月11日 04:04/ 0 赞/ 161 阅读

相关 Leetcode算法Java全解答--32. 最长有效括号

Leetcode算法Java全解答–32. 最长有效括号文章目录 Leetcode算法Java全解答--32. 最长有效括号题目

怼烎@/ 2022年04月13日 14:20/ 0 赞/ 196 阅读