[leetcode/lintcode 題解] 阿裡算法面試真題：最長有效括号

描述

有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭，需要得到的小段的數目至少為k。給出一個隻包含'(' 和')'的字元串，找出其中最長的左右括号正确比對的合法子串。

線上評測位址：

領扣題庫官網

樣例1
輸入: "(()"
輸出: 2
解釋: 最長有效括号子串為 "()"           

樣例2
輸入: ")()())"
輸出: 4
解釋: 最長有效括号子串為 "()()"           

考點

• dp

題解

一般對于最長XX問題容易想到利用DP求解，在這題中利用逆向DP，設狀态dpi為從i到len - 1中，以i開頭的最長合法子串長度：

• 初始化：dplen - 1= 0
• 如果si= ')'，則跳過，因為不可能有由'('開頭的串
• 如果si= '('，則需要找到右括号和它比對，可以跳過以i + 1開頭的合法子串，則需要看j = i + dpi + 1+ 1是否為右括号。如果沒越界且為右括号，那麼有dpi= dpi + 1+ 2，此外在這個基礎上還要将j + 1開頭的子串加進來（隻要不越界）

class Solution {
public:
    int longestValidParentheses(string s) 
    {
        if(s.size() <= 1)   return 0;
        int res = 0;
        vector<int> dp(s.size(), 0);    //初始化
        for(int i = s.size() - 2; i >= 0; i--)
        {
            if(s[i] == '(')                                //如果s[i] = '('，則需要找到右括号和它比對，可以跳過以i + 1開頭的合法子串，則需要看j = i + dp[i + 1] + 1是否為右括号
            {
                int j = i + dp[i + 1] + 1;
                if(s[j] == ')' && j < s.size())        //如果沒越界且為右括号
                {
                    dp[i] = dp[i + 1] + 2;
                    if(j + 1 < s.size())  //還要将j + 1開頭的子串加進來
                        dp[i] += dp[j + 1];
                }    
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};           

更多題解參考：

九章官網solution