leetcode32. 长有效括号

2020-06-19 00:00:00 专区 动态 规划 括号 解题

1. 题目描述


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

示例 1:

输入: "(()"
输出: 2
解释: 长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 长有效括号子串为 "()()"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-valid-parentheses


2. 解题思路


/*
解题思路:
/*
动态规划解题四个组成部分
1. 确定状态
- 研究优策略的后一步
- 化为子问题
dp[i]: 表示s[i]的长有效字符串
2. 转移方程
- 根据子问题定论直接得到
2.1、当s[i]=='(',不构成长有效串,跳过。
2.2、当s[i]==')' 并且s[i-1]=='(',即“.....()”
dp[i] = dp[i-2]+2;
2.3、当s[i]==')' 并且s[i-1]==')', 即“.....))”
dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2

3. 初始条件和边界情况
- 细心,考虑周全
2.2中,i-2可能越界
2.3中,i-dp[i-1]-1、i-dp[i-1]-2可能越界
4. 计算顺序
- 利用之前的计算结果
*/
*/


3. 测试结果

解法一、动态规划


4. 动态规划


/*
title: leetcode32. 长有效括号
author: xidoublestar
method: 动态规划
type: C++
date: 2020-6-9
*/

class Solution {
public:
int longestValidParentheses(string s) {
int size = s.length();
if (size < 2)
return ;
int maxLen = ;
vector<int> dp(size, );
for (int i = 1; i < size; i++)
{
if (s[i] == '(')
continue;
if (s[i - 1] == '(')
dp[i] = (i - 2 >= ? dp[i - 2] : ) + 2;
else if ((i - dp[i - 1] - 1) >= && s[i - dp[i - 1] - 1] == '(')
dp[i] = (i - dp[i - 1] - 2 >= ? dp[i - dp[i - 1] - 2] : ) + dp[i - 1] + 2;
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
};


6. 动态规划

解法一、顺序合并
时间复杂度:O(n)
空间复杂度:O(n)


相关文章