玩命加载中 . . .

32.最长有效括号


问题

传送门:https://leetcode.cn/problems/longest-valid-parentheses/

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

none
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"

示例 2:

none
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

示例 3:

none
输入:s = ""
输出:0

思路:动态规划

由于同样是字符串处理问题,我们先考虑动态规划:设置$dp$数组,其中$dp[i]$表示以$s[i]$结尾的最长有效子串长度。显然,当$s[i]=’(‘$时,$dp[i]=0$。接下来考虑$s[i]=’)’$的情况。为了方便后续讨论,记$dp[i-1]=l_{i-1}$。

  • 若$s[i-1]=’(‘$,则$s[i-1:i]=()$,它们已经有效,因此只需考虑以$s[i-2]$结尾的最长有效子串,拼接起来即可,即$dp[i]=dp[i-2]+2$;
  • 若$s[i-1]=’)’$,则子串$s[i-l_{i-1}:i-1]$一定就是以$s[i-1]$结尾的最长有效子串,那么加上$s[i]=’)’$会怎么样呢?此时需要考虑$s[i-l_{i-1}-1]$了。
    • 若$s[i-l_{i-1}-1]=’(‘$,那么子串$s[i-l_{i-1}-1:i]$仍然有效,则只需考虑以$s[i-l_{i-1}-2]$结尾的最长有效子串,即$dp[i]=dp[i-l_{i-1}-2]+l_{i-1}+2$;
    • 若$s[i-l_{i-1}-1]=’)’$,那么必然不存在以$s[i]$结尾的非空子串,否则与“子串$s[i-l_{i-1}:i-1]$一定就是以$s[i-1]$结尾的最长有效子串”矛盾,故$dp[i]=0$。

状态转移

综上所述,状态转移方程表述为

代码

c++
class Solution {
public:
    int dp[30005];
    string S;
    int DP(int i) {
        if(i < 0)   return 0;
        if(dp[i] != -1) return dp[i];
        if(S[i] == '(') return dp[i] = 0;
        // S[i] == ')'
        if(S[i-1] == '(') {
            return dp[i] = DP(i-2) + 2;
        } else {
            // ((()()))
            int k = DP(i-1);
            if(dp[i] = i-k-1 >= 0 && S[i-k-1] == '(') {
                return dp[i] = k + 2 + DP(i-k-2);
            } else  return dp[i] = 0;
        }
    }
    int longestValidParentheses(string s) {
        if(s.size() == 0 || s.size() == 1) return 0;
        memset(dp, -1 ,sizeof(dp));
        S = s;
        int i;
        dp[0] = 0;
        if(s[0] == '(' && s[1] == ')')  dp[1] = 2;
        else    dp[1] = 0;
        int ans = max(dp[0], dp[1]);
        for(i=2; i<s.size(); i++) {
            dp[i] = DP(i);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

文章作者: 鹿卿
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 鹿卿 !
评论
Powered By Valine
v1.5.2