最长的括号子串

[编程题]最长的括号子串

热度指数：83749 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .

例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .

字符串长度： $0 \le n \le 5*10^5$

要求时间复杂度 $O(n)$ ,空间复杂度 $O(n)$ .

示例1

输入

"(()"

输出

示例2

输入

"(())"

输出

算法知识视频讲解

Maokt

发表于 2021-07-12 11:44:38

精华题解算法思想一：栈解题思路：主要通过栈，可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。具体做法是始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下展开全文

牛客题解官

发表于 2022-04-22 12:52:04

精华题解题目主要信息：一个长度为nnn的仅包含左右括号的字符串计算最长的格式正确的括号子串的长度举一反三：学习完本题的思路你可以解决如下题目： BM65 最长公共子序列(二) BM66.最长公共子串 BM71.最长上升子序列(一) BM73 最长回文子串 BM75 编辑距离(一) BM76 正则展开全文

SandMonth

发表于 2021-07-09 19:14:13

精华题解最长的括号子串给出一个仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。对于字符串"(()"来说，最长的格式正确的子串是"()"，长度为2.再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是" 展开全文

未来0116

发表于 2021-07-14 16:44:39

精华题解一.题目描述NC49最长的括号子串题目链接:https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=196&&tqId=37079&rp=1&ru=/activity/oj& 展开全文

飛魚&鳥

发表于 2020-09-03 21:12:07

dp[i]表示以i结尾最长合法字符串。如果s[i]=='('时该字符串一定不合法；当s[i]==')'时，假设存在解，那么该右括号与其对应的左括号之间的字符串一定是合法的。因此对于i-1的位置，以i-1结尾的合法字符串的开头下标为i - dp[i - 1]，当其前一个位置s[i - 1 - dp[i 展开全文

LifelongCode

发表于 2021-01-11 13:37:12

力扣官方题解: https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/ 解法一：动态规划思路和算法：复杂度分析时间复杂度展开全文

ChunLin233

发表于 2021-07-22 23:28:19

动态规划：g[i]表示以s[i]结尾的最长合法字符串的长度；令d[i]为以s[i]结尾的最长合法字符串的首下标，d[i]=i+1-g[i]；使用变量maxlen跟踪最长字符串长度。已知g[i-1]，计算g[i]：若s[i]=='('，则g[i]==0; 若s[i]==')’，检查下标为d[i-1 展开全文