leetcode 链接：32. 最长有效括号

题目

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

示例：

  1. 输入：s = "(()"
  2. 输出：2
  3. 解释：最长有效括号子串是 "()"
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

输入：s = ""
输出：0

解答 & 代码

动态规划

  • 设置数组 dp，dp[i] 代表以 s[i] 结尾的有效括号长度
  • 状态转移：
    • 如果当前字符 s[i] == '('，则 dp[i] = 0
    • 如果当前字符 s[i] == ')'
      • case 1：若前一个字符 s[i-1] == '(' ，则 s[i-1] 和 s[i] 配对，因此状态转移方程： dp[i] = dp[i-2] + 2（注意额外考虑 i-2 < 0 的情况，若 i-2 < 0，则 dp[i] = 2）
      • case 2：若前一个字符 s[i-1] == ')' ，则找到和 s[i-1] 配对的字符的前一个字符 s[i - 1 - dp[i - 1]]，如果 s[i - 1 - dp[i - 1]] == '('，则可以和当前字符 s[i] 匹配，因此 状态转移方程：dp[i] = dp[i - 1 - dp[i - 1] - 1] + dp[i - 1] + 2（注意还要额外考虑 i - 1 - dp[i - 1] 和 i - 1 - dp[i - 1] - 1 是否小于 0 的问题）
  • 初始化：dp[0] = 0

可以用例子 "(()())(" 分析

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        int maxSubLen = 0;            // 最长有效括号的长度
        // 动态规划数组，dp[i] 代表以 s[i] 结尾的有效括号长度
        vector<int> dp(len, 0);        
        for(int i = 1; i < len; ++i)
        {
            // 只有当前字符为 ')' 时，有效括号长度才可能不为 0
            if(s[i] == ')')
            {
                // 若前一个字符为 '('，则 dp[i] = dp[i-2]+2，但要考虑 i-2 小于 0 的特殊情况
                if(s[i - 1] == '(')
                    dp[i] = i -2  >= 0 ? dp[i - 2] + 2 : 2;
                // 若前一个字符为 ')
                else if(s[i - 1] == ')' )
                {
                    // 若字符 s[i - 1 - dp[i - 1]] == '('，也能配对
                    // dp[i] = dp[i - 1 - dp[i - 1] - 1] + dp[i - 1] + 2
                    // 但要额外考虑下标小于 0 的情况
                    if(i - 1 - dp[i - 1] >= 0 && s[i - 1 - dp[i - 1]] == '(')
                        dp[i] = (i - 1 - dp[i - 1] - 1 >= 0 ? dp[i - 1 - dp[i - 1] - 1] : 0) + dp[i - 1] + 2;
                }
                maxSubLen = dp[i] > maxSubLen ? dp[i] : maxSubLen;
            }
        }
        return maxSubLen;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 85.57% 的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了 22.20% 的用户