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