【leetcode】32.longest-valid-parentheses（最长有效括号）

32.longest-valid-parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
           

32.最长有效括号

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

示例 1:

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

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

思路：

分析计算的流程，可以得到两种状态：

I. 括号匹配时，判断前一个是否为 ')' 。如果是，则加上对应的数值。
     ( ( ( ) ) )
     0
     0 0
     0 0 0
     0 0 0 2
     0 0 0 2 4
     0 0 0 2 4 6

     II. 匹配了一组括号后，累计前面的有效长度。（偏移距离为：i - 当前括号匹配串的长度）
     ( ) ( ) ( )
     0
     0 2
     0 2 0
     0 2 0 4
     0 2 0 4 0
     0 2 0 4 0 6
           

1. 由状态 II 可知，计算状态 I 时公式为：num[i] = 2 + num[i-1];
2. 状态 II 的计算公式：num[i] += num[i - num[i]]; // 必须先计算状态 I 等到当初括号匹配子串的长度。
3. 由此可知：

num[i] = 2 + num[i-1];              // 只计算状态 I
     num[i] += num[i - num[i]];          // 结合前一步算状态 II
     num[i] = (2 + num[i-1]) + num[i - (2 + num[i-1])];  // 整合前面两步。
     num[i] = (2 + (i?num[i-1]:0)) + (i > (2 + (i?num[i-1]:0)) ? num[i - (2 + (i?num[i-1]:0))] : 0); // 加入 i 有效性判断
           

CODE：

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length();
        int ret = 0;
        if (len <= 1)   return ret;
        int num[len] = { 0 };
        int cnt = 0;

        for (int i = 0; i < len; ++i) {
            char ch = s[i];
            num[i] = 0;
            if (ch == '(') {
                ++cnt;
            } else if (cnt) {
                --cnt;
                // num[i] = 2 + ((i > 0) ? num[i - 1] : 0);
                // num[i] += (i > num[i]) ? num[i - num[i]] : 0;
                num[i] = (2 + (i?num[i-1]:0)) + (i > (2 + (i?num[i-1]:0)) ? num[i - (2 + (i?num[i-1]:0))] : 0);
                ret = max(num[i], ret);
            }
        }
        return ret;
    }
};