0032 - Longest Valid Parentheses
题干
破题
考虑合法的括号序列的性质：
- 开括号可以任意数量地出现，但是串结束的时候括号可能没有匹配完
- 闭括号不能超出开括号的数量
- 括号序列是对称的，从反方向来看，闭括号就是开括号，开括号就是闭括号
给出一个 括号单元 的递归定义：unit ::= () | (unit+)
一个合法的括号串： s=unit*
链接题目
解①双向扫描：
一个只包含左右括号的串总是由三部分组成：括号单元、失配的闭括号、尾部的未完成的括号单元。
- 与前面出现的开括号数量匹配的闭括号属于括号单元；
- 其余的闭括号属于失配的闭括号；
- 而多余的开括号如果一直到最后都没有被匹配，就会形成未完成的括号单元
对于括号单元和失配闭括号，一遍扫描就可以解决：统计开括号和闭括号，当数量相等时就是一个括号单元的结束，当遇到失配闭括号时就重置开括号闭括号数量。
但是对于尾部可能存在的未完成的括号单元，用子串 $s_1$ 表示，因为需要统计未完成的括号单元内的最长括号序列，前面的算法处理不了1，但是如果从反方向看2它尾部的未完成单元，它的尾部一定不存在未完成单元3，因此可以一遍扫描计算得到这一部分的最长的合法括号序列。
def solve(s: str) -> int:
open = 0
close = 0
start = -1
ans = 0
for i, c in enumerate(s):
if c == '(':
if open == close:
start = i
open += 1
elif c == ')':
close += 1
if close > open:
# reset
open = 0
close = 0
elif close == open:
ans = max(ans, open*2)
if open > close:
rev_open = 0
rev_close = 0
rev_ans = 0
for c in s[start+1:][::-1]:
if c == ')':
rev_open += 1
elif c == '(':
rev_close += 1
if rev_close > rev_open:
# reset
rev_open = 0
rev_close = 0
elif rev_close == rev_open:
rev_ans = max(rev_ans, rev_open*2)
ans = max(ans, rev_ans)
return ans
时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ，是空间复杂度最优的解。
解②DP：
按照扫描方向看，用后缀数组 $\text{dp}[i]$ 表示结尾在 $i$ 处的最长合法括号序列的长度。
- 如果结尾字符是
(，对应 $\text{dp}$ 一定为 $0$ ； - 否则结尾字符是
)，这时需要检查前一个字符对应的最长合法括号序列，如果在那个括号序列的前一个字符 $s[i-\text{dp}[i-1]-1]$ 又是(，则此时的 $\text{dp}[i] = 2+\text{dp}[i-1]$ ，如果此时 $i-\text{dp}[i-1]-1 \gt 0$ ，就再加上 $\text{dp}[i-\text{dp}[i-1]-2]$ ，否则没有匹配的开括号，对应 $\text{dp}$ 也为 $0$ 。
def solve(s: str) -> int:
if not s:
return 0
dp = [0] * len(s)
for i in range(1, len(s)):
if s[i] == ')' and i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
dp[i] = 2 + dp[i-1] + (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0 else 0)
return max(dp)
时间复杂度 $O(n)$ ，空间复杂度 $O(n)$
前面双向扫描也可以叫做两遍扫描，而 DP 方法只需要扫描一遍，时间性能更优。
解③Stack：
如果保存开括号的索引位置，那么当遇到闭括号弹出的时候，就可以计算这一对儿括号序列的长度，但有一个问题是如何计算顶层连续的括号单元？
这里使用了一个简单、但是 Tricky 的方法，保持第一个入栈的开括号前一个字符的位置在栈里，遇到闭括号时弹出开括号，当遇到失配的闭括号时，就弹出这个位置，如果栈为空，那就把当前位置入栈，如果下一个字符不是开括号就继续弹出并压入新的失配闭括号，直到遇到新的开括号，开启新的括号单元的序列。
def solve(s: str) -> int:
stack = [-1] # 保存两个信息，记录连续信息
ans = 0
for i, c in enumerate(s):
if c == '(':
stack.append(i)
else:
stack.pop()
if stack:
ans = max(ans, i - stack[-1])
else:
stack.append(i)
return ans
时间复杂度 $O(n)$ ，空间复杂度 $O(n)$
单位比较次数更少，时间性能最佳。
注解
