LeetCode 32. Longest Valid Parentheses (最长有效括号)

╰+哭是因爲堅強的太久メ 2022-05-11 04:04 99阅读 0赞

题目描述：

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

示例：

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

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

Accepted C++ Solution:

1.使用栈stack

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size(), longest = 0;
            stack<int> st;
            for (int i = 0; i < n; i++) {
                if(s[i] == '(') st.push(i);
                else {                        //s[i] = ')'
                    if(!st.empty()) {
                        if(s[st.top()] == '(')    st.pop();
                        else    st.push(i);
                    }
                    else st.push(i);
                }
            }
            
            if(st.empty())  longest = n;
            else {
                int a = n, b = 0;
                while(!st.empty()) {
                    b = st.top(); st.pop();
                    longest = max(longest,a-b-1);    //计算每个间隔之间的长度
                    a = b;
                }
                longest = max(longest,a);
            }
            return longest;
        }
    };

遇到 '(' or 遇到 ’)' 但是栈顶元素不为'(' 则把下标i压入栈中，代表着一个间隔。

计算最后栈中每个下标之前的间隔，就能得到最大的有效括号长度。

2.动态规划

思路:

如果s \[i\]是'('，将dp\[i\]设置为0，因为任何字符串以'('不是有效字符串结尾。  
  
如果s \[i\]是')'

if, s \[i-1\]='('，**dp\[i\] =dp\[i-2\] + 2**

Else if, s\[i-1\] == ')' && s\[i-dp\[i-1\]-1\] == '(',  **dp\[i\] = dp\[i-1\] + 2 + dp\[i-dp\[i-1\]-2\]**

例如，输入“()(())”，在i = 5时，dp数组是\[0,2,0,0,2,0\]，dp\[5\] =dp\[4\] + 2 +dp\[1\] = 6

class Solution {
    public:
        int longestValidParentheses(string s) {
                if(s.length() == 0)
                        return 0;
                int curMax = 0;
                vector<int> dp(s.size(),0);
                for(int i =1; i < s.length(); ++i) {
                        if(s[i] == ')') {
                                if(s[i-1] == '(') {
                                        dp[i] = (i-2) >= 0 ? (dp[i-2]+2) : 2;
                                        curMax = max(dp[i],curMax);
                                }
                                else {
                                        if(i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' ) {
                                                dp[i] = dp[i-1] + 2 + ((i-dp[i-1]-2 >= 0) ? dp[i-dp[i-1]-2] : 0);
                                                curMax = max(dp[i],curMax);
                                        }
                                }
                        }
                }
                return curMax;
        }
    };