leetcode32. 长有效括号

2020-06-19 16:49:25

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;
    }
};