[Leetcode] 32. Longest Valid Parentheses 解題報告

題目：

Given a string containing just the characters 

'('

 and 

')'

, find the length of the longest valid (well-formed) parentheses substring.

For 

"(()"

, the longest valid parentheses substring is 

"()"

, which has length = 2.

Another example is 

")()())"

, where the longest valid parentheses substring is 

"()()"

, which has length = 4.

思路：

        這種求極值的問題很多情況下都可以采用動态規劃加以解決，本題也不例外。可是對dp的不同定義卻可以導緻非常不同的時間複雜度。這裡提供幾種不同的思路：

1、二維動态規劃：dp[i][j]表示從i到j之間的字元串是否可以構成合法的括弧對，則遞推公式為：

        1）如果dp[i+1][j-1] == true，并且s[i] == '(' && s[j] == ')'，則dp[i][j] = true;

        2）如果存在i < k < j，使得dp[i][k] == true && dp[k+1][j] == true，則dp[i][j] = true。

        如果dp[i][j]為true，則可以更新目前得到的最長合法括号長度。可惜這種思路的時間複雜度高達O(n^3)，空間複雜度為O(n^2)，無法通過Leetcode上面的大資料。

2、一維動态規劃+棧：利用棧來保證左括弧的數目不小于右括弧的數目（這是括弧對合法的必要條件）并且記錄目前左括弧的位置。定義dp[i + 1]表示以i 為結尾的最長合法括弧對的長度。根據左右括弧比對的性質，思路為：

        1）如果字元串中目前字元為‘(’，則将其位置入棧，代表這個位置需要有一個比對的右括弧；

        2）如果字元串中目前字元為')'，則檢查棧：

              a）如果此時棧為空，說明目前段的字元串是不合法的；

              b）如果此時棧不為空，則說明目前的右括弧可以被比對，并且dp[i+1] = (i - j + 1) + dp[j]。其中（i - j + 1）表示從目前字元到棧頂元素的長度，而dp[j]表示棧頂元素之前的合法子字元串的長度。該思路的時間複雜度為O(n)，空間複雜度為O(n)。

3、一維動态規劃：仔細推敲2的思路，發現實際上對于dp[i+1]而言，通過dp[i]可以推導出能夠和s[i] == ')' 比對的左括弧的索引值為(i - dp[i] - 1)。那麼我們就不再需要開辟棧空間了，而是可以直接推導出dp[i+1]和dp[i]之間的遞推關系：dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2。該算法的時間和空間複雜度同2。

4、棧：事實上')'也是可以作為分界符入棧的。如果目前字元為')'，則試圖在棧中尋找和它比對的'('的左括弧。如果找到相對應的左括弧，則首先彈棧（為什麼要先彈棧？ 考慮()()的情況），然後可以知道以‘)’結尾的合法括弧對的長度為st.empty() ? i + 1 : i - st.top()。而不以該')'結尾的合法最長合法括弧對的長度為在此前已經被記錄下來了，是以此時隻需要更新其值即可。一旦無法找到和目前')'比對的左括弧，則将該')'入棧作為分界符，使得後來的右括弧無法再與目前棧中非棧頂的左括弧相比對。這個思路确實很精妙，雖然 理論上時間複雜度和空間複雜度仍然為O(n)，但事實上在大多數情況下空間複雜度會遠小于O(n)。

代碼：

一維動态規劃+棧：

class Solution {
public:
    int longestValidParentheses(string s) 
    {
        if(s.size() == 0) 
            return 0;  
        stack<int> st;  
        vector<int> dp(s.size() + 1, 0);
        int ret = 0, len= 0;  
        for(int i = 0; i < s.size(); i++)  
        {  
            if(s[i] == '(') 
            {
                st.push(i);  
            }
            else  
            {  
                if(!st.empty())
                {
                    dp[i + 1] = (i - st.top() + 1) + dp[st.top()];  
                    st.pop();  
                    ret = max(dp[i + 1], ret);  
                }
            }  
        }  
        return ret;  
    }
};
           

一維動态規劃：

class Solution {
public:
    int longestValidParentheses(string s) 
    {
        int ret = 0;
        // dp[i] means the length of the longest valid parenthese that ends with s[i]
        vector<int> dp(s.size() + 1, 0);  
        for(int i = 1; i < s.size(); i++)  
        {  
            if(s[i]=='(') 
                continue;  
            // now we know s[i] == ')'
            // (i - dp[i] - 1) is the index of the '(' that will match with s[i]
            if(i - dp[i] - 1 >= 0 && s[i - dp[i] - 1] =='(')   
                dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2;  
            ret = max(ret, dp[i + 1]);  
        }  
        return ret;  
    }
};
           

棧：

class Solution {
public:
    int longestValidParentheses(string s) 
    {
        int ret = 0;  
        stack<int> st;  
        for(int i = 0; i < s.size(); i++)  
        {  
            if(s[i]=='(') 
            {
                st.push(i); 
            }
            else    // s[i] == ')'
            {
                if(!st.empty() && s[st.top()]=='(')
                {
                    st.pop();  
                    ret = max(st.empty() ? i + 1 : i - st.top(), ret);
                }
                else
                {
                    st.push(i);
                }
            }
        }  
        return ret;  
    }
};