编程题 34 /48

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

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

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

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

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

参考答案

方法一：栈。

1、对于遇到的每个‘(’ ，将它的下标放入栈中
2、对于遇到的每个 ‘)’ ，先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
3、从前往后遍历字符串并更新答案即可。

方法二：动态规划。

定义dp[i]为以i结尾的合法括号子串的最大长度。

1、s[i] = ')' 且 s[i-1] = '('，表示字符串形如 ‘......()’，则可推出：dp[i] = dp[i-2] + 2

以进行这样的转移，是因为结束部分的 "()" 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2

2、s[i] = ')' 且 s[i-1] = ')'，表示字符串形如 ‘......))’，则可推出：如果s[i - dp[i-1] - 1] = '('，则 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

纠错收藏

查看讨论

1
...
29
30
31
32
33
34
35
36
37
38
39
...
48
跳转到

上一题下一题