☆打卡算法☆LeetCode 32、最长有效括号 算法解析
☆打卡算法☆LeetCode 32、最长有效括号 算法解析
恬静的小魔龙
发布于 2022-08-07 09:57:51
发布于 2022-08-07 09:57:51
一、题目
1、算法题目
“给定一个字符串，找出最长有效的字符串的长度。”
题目链接：
来源：力扣（LeetCode）
链接：32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入： s = "(()"
输出： 2
解释： 最长有效括号子串是 "()"示例 2：
输入： s = ")()())"
输出： 4
解释： 最长有效括号子串是 "()()"二、解题
1、思路分析
这个题可以使用动态规划思路解题。
定义dp[i]表示以下标i字符结束的最长有效字符串长度，因此左括号在dp中的值必定为0，那么只需要知道右括号在dp数组中的位置。
遍历字符串求解dp值，每两个字符检查一次，如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 subs ），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 subs 的前面）。因此，如果子字符串 subs 的前面恰好是 ‘(’ ，那么我们就用 2 加上 subs 的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 “(subs )” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。
最后的答案即为 dp 数组中的最大值。
2、代码实现
代码参考：
public class Solution {
public int LongestValidParentheses(string s) {
int left = 0, right = 0, ans = 0;
int n = s.Length;
for (int i = 0; i < n; i++)
{
if (s[i] == '(')
left++;
else
right++;
if (left == right)
ans = Math.Max(ans, right);
else if (right > left)
left = right = 0;
}
left = right = 0;
for (int i = n-1; i >=0; i--)
{
if (s[i] == '(')
left++;
else
right++;
if (left == right)
ans = Math.Max(ans, left);
else if (left > right)
left = right = 0;
}
return ans * 2;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n)
其中n为字符串的长度，只需要遍历一遍字符串即可求出dp数组。
空间复杂度： O(n)
我们需要一个大小为n的dp数组。
三、总结
这道题很适合用动态规划来解题，因为有最长这个字眼，用动态规划解这道题，需要先确定状态。
然后根据状态转移方程，根据初始条件和边界去实现过程。
需要注意的是计算顺序。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-10-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录