LeetCode-最长有效括号

题目：最长有效括号

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣(LeetCode)

算法：动态规划

解法：

定义 $dp[i]$ 表示以第i个字符结尾的字符串中最长的有效括号长度。

example1:

string: "()()()"
index  : 0 1 2 3 4 5
dp:      0 2 0 4 0 6

example2:

string: "()((())"
index  : 0 1 2 3 4 5 6 
dp:      0 2 0 0 0 2 4

example3:

string: "()(())"
index: 0 1 2 3 4 5
dp:    0 2 0 0 2 6

1. 若$s[j] = ($, 由于(不可能是有效括号的结束字符，所以$dp[j] = 0$。
2. 若$s[j] = )$，存在多种情况
   • 若$s[j-1]为($， 若是则可以组成有效括号，有效括号长度+2。
   • 若$s[j-1]为)$， 也不一定不是有效括号，还可能存在括号嵌套的情况，如”example2”, 这种情况则要判断 $s[dp[j-1] - 1]$是否等于(，是则+2。该情况可以和上一种情况合并，都可表示为判断 $s[dp[j-1] - 1] == ($ 是否成立。
3. 当 $dp[j]$是有效括号的结束字符时，要判断是否和之前的有效括号连续，如果连续要加上之前的长度。如”example3”， $s[5]= )$, 且 $s[5 - dp[4] - 1] = ($, 所以 $dp[5] = dp[4] + 2 = 4$。但是由于可以和之前的”()”连起来，所以 $dp[5] = dp[4] + 2 + dp[5 - dp[4] - 2] = 6$。

状态转移方程

$$
dp[i]=
\left\{
\begin{align}
&0,&s[i]=(\\\
&0,&s[i]= ) \quad \&\& \quad s[i-dp[i-1]-1] \neq (\\\
&dp[i-1] + 2 + dp[i-dp[i-1]-2], &s[i]= ) \quad \&\& \quad s[i-dp[i-1]-1] = (\\\\
\end{align}
\right.
$$

时间复杂度&空间复杂度

1. 时间复杂度: $O(n)$
2. 空间复杂度: $O(n)$

LeetCode执行结果

• 执行用时 : 4 ms, 在所有 C++ 提交中击败了 95.63%的用户。
• 内存消耗 : 9.8 MB, 在所有 C++ 提交中击败了 15.58%的用户。

感受

其实动规比较简单，有套路可循。尤其是和字符串有关的题目，基本都与子串有关。但是难在子问题的划分，比如这道题中定义 $dp[i]$ 表示以第i个字符结尾的字符串中最长的有效括号长度，这样就比较简单。而我之前想的是定义为子串中最长有效括号的长度，到后面很难处理。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
&#123;
public:
    int longestValidParentheses(string s)
    &#123;
        if(s.empty())
        &#123;
            return 0;
        &#125;

        vector<int> dp(s.length(),0);
        dp[0] = 0;
        for(int i=1; i<s.length(); i++)
        &#123;
            if(s[i] == ))
            &#123;
                if(i - dp[i-1] -1 >= 0 &&  s[i - dp[i-1] -1] == ()
                &#123;
                    if(i - dp[i-1] -2 >=0)
                    &#123;
                        dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] -2];                    
                    &#125;
                    else
                    &#123;
                        dp[i] = 2 + dp[i-1];                    
                    &#125;                    
                &#125;                
            &#125;    
            else
            &#123;
                dp[i] = 0;
            &#125;
        &#125;
        return *max_element(dp.begin(), dp.end());
    &#125;
&#125;;

int main()
&#123;
    string str;
    std::cout << "input:";
    std::cin >> str;
    Solution s;
    std::cout<<s.longestValidParentheses(str)<<std::endl;
    return 0;
&#125;