Leetcode-32.最长有效括号

发表于 分类于 阅读次数：

题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

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

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

解法1：动态规划

1.状态

创建一维dp数组,dp[i]表示i位置能构成的括号匹配子串长度,

即若s[i]=’(‘则dp[i]必然为0

2.状态转移方程

当 s[i]=’)’ 时

​ 1）当s[i-1]=’(‘时 dp[i]=dp[i-2]+2; if(i<2 dp[i]=2) //因为i<2且出现这种情况则只有开头为（）才会出现

​ 2）当s[i-1]=’)’时 ;

·当 (i-dp[i-1]>0&&dp[i-dp[i-1]-1]==’(‘) 则dp[i]=dp[i-1]+dp[i-dp[i-1]-1-1]+2；若i-dp[i-1]<2 则dp[i]=dp[i-1]+2; //因为只有开头为(())时 才会出现这种情况

·当 (dp[i-dp[i-1]-1]==’)’) 则dp[i]=0;

为何状态转移方程为这个式子

​ s[i-1]=’(‘很好理解。

主要是s[i-1]=’)’

​ 以（（））为例 i=3 s[i]=’)’ s[i-1]=’)’ 若想知道当前dp[i]的值， 已设dp表示i位置能构成的括号匹配子串长度，假设有个’(‘跟s[i]匹配，那么咱们现在要找到它的位置，如何找到呢，dp[i-1]已经算出来，dp[i-1]表示i-1位置匹配的子串长度，那么让i-dp[i-1]-1就找到了前面那一个未匹配的字符,如果这一字符又刚好是’(‘则正好和s[i]匹配，

dp[i]=前一个位置匹配的子串长度+左括号前一位位置匹配的字符长度+这一对括号的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestValidParentheses(string s) {
        int i,max=0;
        int n=s.length();
        vector<int>dp(n,0);
        for(i=1;i<n;i++)
        {
            if(s[i]==')')
            {
                if(s[i-1]=='(')
                {
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }
                else if(i-dp[i-1]>0)
                {
                    if(s[i-dp[i-1]-1]=='(')
                        dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-1-1]:0)+2;
                }
                max=max>dp[i]?max:dp[i];
            }
        }
        return max;
    }
};