LeetCode: 32. Longest Valid Parentheses

引言

题目链接:https://leetcode.com/problems/longest-valid-parentheses/

题目大意

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

  • Example

题解

明确一个要点,一个匹配的字符串一定是以 ')' 结尾

假设 dp[i] 表示从字符串开头以第i位结尾的子字符串的最大匹配长度,每次读取到为 ')' 的字符串只需要判断第 i-1-dp[i-1] 对应索引是否为 '(' 即可

于是有如下状态转移方程

再进行dp时注意维护最大值即可,为了避免越界情况,博主采取在目标字符串头部添加一个无效字符。

复杂度

时间复杂度 O(n)

空间复杂度 O(n)

AC代码

c++版本

go版本


繁夜