LeetCode第32題: 最長有效括號 longestValidParentheses(C語言)

思路1：這個序列問題，很容易聯(lián)想到用動態(tài)規(guī)劃的思路來解最長公共字符串的問題庶近，區(qū)別在于枢纠，在求最長公共字符串的時候，子狀態(tài)從兩個相鄰字符開始判斷筹裕，如果這兩個字符不相等，則包含這兩個相鄰字符的一定不是公共字符串窄驹。而對于本題朝卒，如果兩個相鄰的括號不匹配，比如兩個都是'('乐埠、'('抗斤，這兩個不匹配，但以這兩個子串為基礎(chǔ)的其他子串不一定無法組成有效的括號丈咐，比如連續(xù)四個括號分別為'( ( ) )'這樣的形式瑞眼，無法從之前計算的兩個右括號不匹配的情況推出現(xiàn)在四個括號的匹配情況。那么問題來了棵逊，針對本題的最優(yōu)子狀態(tài)應(yīng)該怎么去找呢伤疙？
通過分析：兩個匹配的左右括號，一定是相鄰最近的匹配對辆影，也就是最里層的括號一定是優(yōu)先匹配徒像，然后在逐層向外匹配，比如上述的四個連續(xù)括號'( ( ) )'的情況蛙讥，一定是中間兩個先匹配锯蛀，然后再匹配外層的兩個。如果我們在匹配第一個'('的時候键菱，已經(jīng)提前知道第二個和第三個已經(jīng)組合為一個有效括號的話谬墙，那第一個就可以直接去匹配第四個左括號了，這樣的話经备，對于第一個右括號拭抬，最長匹配有效括號長度就是4。
也就是說侵蒙，如果從左邊第一個匹配的時候造虎，提前知道他右側(cè)的已經(jīng)匹配匹配好的最大長度了，那么就可以跳過已經(jīng)匹配完成的情況了纷闺，比如'( ( ( ) ) )'這個情況算凿，在匹配第一個右括號的時候份蝴，已經(jīng)知道中間的兩個括號對的話，則直接跳過氓轰，去匹配第六個做括號婚夫，即可得出最長匹配有效括號長度是6。
我們可以嘗試從字符串的末端先提前生成上述兩個情況的字符串匹配的結(jié)果署鸡，首先建立一個與輸入字符串等長的數(shù)組a案糙，用于保存每個字符串位置能匹配到的最長的長度，比如對于'( ( ( ) ) )'當(dāng)計算第一個右括號的時候靴庆，已經(jīng)知道a[1]的值是4时捌，也就是從這個位置向右移動四個位置，可以算作第二個字符的匹配炉抒，所以計算第一個右括號的話奢讨，直接去匹配第五個。這就是我們要設(shè)計的動態(tài)規(guī)劃的子狀態(tài)了焰薄。
這里還有一個問題拿诸，對于'( ( ( ) ) ) ( )'，當(dāng)計算第一個的值時蛤奥，如果跳過這個a[1]的值4的長度之后佳镜，順利匹配到第五個字符僚稿，而且匹配成功了凡桥，但是第五個字符的后面的字符串依然是一個匹配完成的字符串，則還要加上這段長度蚀同，然后再算作第一個字符的整體長度
這就是完整的思路了缅刽。具體代碼如下：

int longestValidParentheses(const char *s)
{
    int n=strlen(s);
    if(n == 0)
        return 0;
    int i,j;
    int dp[n];
    int max=0;
    
    for(i=0;i<n;i++)
        dp[i]=0;
    for(i=n-2;i>=0;i--)
    {
        if(s[i]=='(')
        {
            j=i+1+dp[i+1];
            if(j<n && s[j]==')')
            {
                dp[i]=dp[i+1]+2;
                if(j+1<n)
                    dp[i]+=dp[j+1];
            }
        }
        if(max<=dp[i])
            max=dp[i];
    }
    return max;
}

思路2:在思路1中我們知道，在一個括號序列里蠢络，當(dāng)遇到一個左括號')'時衰猛，需要找到其左側(cè)與其最近的右括號'('，而不是最靠前的右括號'('刹孔，比如輸入序列'( ( ) )'啡省，很明顯第一個')'找到的時候內(nèi)部的右括號'('也就是第二個右括號'('，而第一個右括號'('髓霞，需要等待其右邊沒有待匹配的右括號'('時候才開始匹配卦睹，針對本例，也就是匹配完內(nèi)部的括號對再匹配外側(cè)的括號對方库。
那么结序，當(dāng)我們遇到輸入序列的時候，如果首先遇到一個右括號'('纵潦，
1徐鹤、如果其第二個輸入的是左括號')'垃环，則直接完成匹配；
2返敬、如果其第二個輸入的依然是右括號'('時候呢遂庄？我們是不是就要把第一個輸入的右括號'('掛起，等第二個輸入的右括號'('匹配到后邊的左括號了劲赠，再來匹配被掛起的第一個右括號'('涧团。
遇到這樣的情形，可以將遇到的右括號'('推入棧stack[]數(shù)組中经磅，并記錄stack[top]為輸入序列的索引位置泌绣，每遇到一個左括號')'，則從棧中推出一個右括號'('预厌。

現(xiàn)在問題來了阿迈，我們現(xiàn)在知道如何去找到兩個匹配的括號了，那么轧叽，怎么來計算最長的有效括號呢苗沧，上一步，每一次匹配成功炭晒，我們可以獲取到兩個有效括號對的索引待逞，我們可以新建一個與輸入字符串等長的mark數(shù)組，每遇到一個匹配成功的括號對网严，就將兩個索引標(biāo)記下來识樱。等循環(huán)遍歷完成，統(tǒng)計mark數(shù)組的最長連續(xù)標(biāo)記的長度即可震束。廢話不說了怜庸，上代碼。

int longestValidParentheses(char* s) {
    int len=strlen(s);
    if(len <= 1)
        return 0;
    int* mark=(int*)malloc(sizeof(int)*len);
    for(int i=0;i < len;i++)
        mark[i] = -1;
    int* stack=(int*)malloc(sizeof(int)*len);
    int top=0;
    for(int i = 0; i < len; i++){
        if(s[i]=='(')
            stack[top++]=i;
        else{
            if(top!=0){
                mark[stack[top-1]]=0;
                mark[i]=0;
                top--;
              }
          }
    }
          
    int count=0;
    int newCount=0;
    for(int i = 0; i < len;i++){
        if(mark[i]!= -1)
            newCount++;
        else{
            if(newCount>count){
                count=newCount;
            }
            newCount=0;
        }
    }
    if(newCount>count)count=newCount;
    return count;
}

本系列文章垢村，旨在打造LeetCode題目解題方法割疾，幫助和引導(dǎo)同學(xué)們開闊學(xué)習(xí)算法思路，由于個人能力和精力的局限性嘉栓，也會參考其他網(wǎng)站的代碼和思路宏榕，如有侵權(quán)，請聯(lián)系本人刪除侵佃。