最长有效括号子串（另一种解法）

字数 2217 2025-10-26 13:29:52

最长有效括号子串（另一种解法）

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

解题过程

问题分析
- 有效括号字符串满足：每个左括号 '(' 必须有对应的右括号 ')'，且子串是连续的。
- 难点在于有效子串可能被无效的括号隔开，例如 "()(()" 中，有两个有效的 "()"，但它们不连续。而 "()(())" 中，最后四个字符形成了一个有效的连续子串 "(())"。
- 我们需要找到最长的那个连续有效子串的长度。
动态规划定义
- 我们定义一个数组 dp，其中 dp[i] 表示 以字符串中第 i 个字符结尾 的最长有效括号子串的长度。
- 注意，这里定义的是 以 i 结尾。如果第 i 个字符是 '('，那么它不可能作为一个有效括号子串的结尾（因为它没有被匹配），所以此时 dp[i] 必然为 0。
- 因此，我们只需要考虑当 s[i] == ')' 时的情况。
状态转移方程推导
情况一：简单相邻匹配
- 形如 ......()。
- 当 s[i] == ')' 且 s[i-1] == '(' 时，这两个字符自然形成一对有效的括号。
- 那么，以 s[i] 结尾的最长有效括号长度，至少是 2。
- 我们还可以把 s[i-2] 结尾的有效长度也连起来。即 dp[i] = 2 + dp[i-2]。
- 例如，字符串 "()()"：
  - i=1 (第二个字符)：s[1]==')' 且 s[0]=='('，所以 dp[1] = 2 + dp[-1]。这里 i-2 = -1，我们将其长度视为 0。所以 dp[1] = 2。
  - i=3 (第四个字符)：s[3]==')' 且 s[2]=='('，所以 dp[3] = 2 + dp[1] = 2 + 2 = 4。正确。
情况二：嵌套匹配
- 形如 ......( (......) )，即一个有效括号子串被另一对括号包裹着。
- 当 s[i] == ')' 且 s[i-1] == ')' 时，情况变得复杂。这表示我们可能遇到了嵌套。
- 我们首先检查与当前 s[i] 对应的潜在左括号的位置。这个位置是 j = i - dp[i-1] - 1。
  - dp[i-1] 是以 s[i-1] 结尾的有效长度，它代表了一串已经匹配好的括号。
  - i - dp[i-1] - 1 就是跳过这串已经匹配好的括号，找到它前面的那个字符。
- 如果 j >= 0 且 s[j] == '('，那么这个 '(' 就能与当前的 ')' 匹配成功！
- 匹配成功后，我们至少形成了 (......) 这样一个有效对，其基础长度是 2。
- 此外，我们还要加上内部嵌套的有效长度 dp[i-1]。
- 最后，不要忘记，在 j 之前可能还有一个有效括号子串，我们可以把它也连起来。这个子串的长度就是 dp[j-1]。
- 因此，状态转移方程为：dp[i] = 2 + dp[i-1] + dp[j-1]，其中 j = i - dp[i-1] - 1。
- 例如，字符串 "()(())"：
  - 我们先计算前面的：i=1 时，dp[1] = 2。
  - i=2 时，字符是 '('，dp[2] = 0。
  - i=3 时，字符是 '('，dp[3] = 0。
  - i=4 时，字符是 ')'，属于情况一。s[4]==')' 且 s[3]=='('，所以 dp[4] = 2 + dp[2] = 2 + 0 = 2。
  - 关键步骤 i=5：字符是 ')'，且 s[4] 也是 ')'，属于情况二。
    - 计算 j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2。
    - 检查 s[2]，它是 '('，匹配成功！
    - 所以 dp[5] = 2 + dp[4] + dp[1] = 2 + 2 + 2 = 6。正确。
算法步骤
1. 初始化一个长度与字符串相同的数组 dp，所有值初始为 0。定义变量 maxLen 记录最终答案，初始为 0。
2. 从索引 i = 1 开始遍历字符串（因为 i=0 是单个字符，有效长度最多为0）。
3. 如果 s[i] == ')'：
  - 情况一：如果 s[i-1] == '('，则 dp[i] = 2 + (dp[i-2] if i >= 2 else 0)。
  - 情况二：如果 s[i-1] == ')' 且 i - dp[i-1] > 0（确保 j 索引有效）且 s[i - dp[i-1] - 1] == '('，则 dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if (i - dp[i-1] - 2) >= 0 else 0)。
4. 在每次计算完 dp[i] 后，更新 maxLen = max(maxLen, dp[i])。
5. 遍历结束后，返回 maxLen。
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度，我们只需要遍历一次数组。
- 空间复杂度：O(n)，我们需要一个长度为 n 的 dp 数组。

这个解法通过精细地分类讨论，利用动态规划记录了以每个位置结尾的有效长度，从而能够准确地计算出全局的最长有效括号子串。

最长有效括号子串（另一种解法）题目描述：给定一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。解题过程问题分析有效括号字符串满足：每个左括号 '(' 必须有对应的右括号 ')'，且子串是连续的。难点在于有效子串可能被无效的括号隔开，例如 "()(()" 中，有两个有效的 "()"，但它们不连续。而 "()(())" 中，最后四个字符形成了一个有效的连续子串 "(())"。我们需要找到最长的那个连续有效子串的长度。动态规划定义我们定义一个数组 dp ，其中 dp[i] 表示以字符串中第 i 个字符结尾的最长有效括号子串的长度。注意，这里定义的是以 i 结尾。如果第 i 个字符是 '('，那么它不可能作为一个有效括号子串的结尾（因为它没有被匹配），所以此时 dp[i] 必然为 0。因此，我们只需要考虑当 s[i] == ')' 时的情况。状态转移方程推导情况一：简单相邻匹配形如 ......() 。当 s[i] == ')' 且 s[i-1] == '(' 时，这两个字符自然形成一对有效的括号。那么，以 s[i] 结尾的最长有效括号长度，至少是 2 。我们还可以把 s[i-2] 结尾的有效长度也连起来。即 dp[i] = 2 + dp[i-2] 。例如，字符串 "()()"： i=1 (第二个字符)： s[1]==')' 且 s[0]=='(' ，所以 dp[1] = 2 + dp[-1] 。这里 i-2 = -1 ，我们将其长度视为 0。所以 dp[1] = 2 。 i=3 (第四个字符)： s[3]==')' 且 s[2]=='(' ，所以 dp[3] = 2 + dp[1] = 2 + 2 = 4 。正确。情况二：嵌套匹配形如 ......( (......) ) ，即一个有效括号子串被另一对括号包裹着。当 s[i] == ')' 且 s[i-1] == ')' 时，情况变得复杂。这表示我们可能遇到了嵌套。我们首先检查与当前 s[i] 对应的潜在左括号的位置。这个位置是 j = i - dp[i-1] - 1 。 dp[i-1] 是以 s[i-1] 结尾的有效长度，它代表了一串已经匹配好的括号。 i - dp[i-1] - 1 就是跳过这串已经匹配好的括号，找到它前面的那个字符。如果 j >= 0 且 s[j] == '(' ，那么这个 '(' 就能与当前的 ')' 匹配成功！匹配成功后，我们至少形成了 (......) 这样一个有效对，其基础长度是 2 。此外，我们还要加上内部嵌套的有效长度 dp[i-1] 。最后，不要忘记，在 j 之前可能还有一个有效括号子串，我们可以把它也连起来。这个子串的长度就是 dp[j-1] 。因此，状态转移方程为： dp[i] = 2 + dp[i-1] + dp[j-1] ，其中 j = i - dp[i-1] - 1 。例如，字符串 "()(())"：我们先计算前面的： i=1 时， dp[1] = 2 。 i=2 时，字符是 '('， dp[2] = 0 。 i=3 时，字符是 '('， dp[3] = 0 。 i=4 时，字符是 ')'，属于情况一。 s[4]==')' 且 s[3]=='(' ，所以 dp[4] = 2 + dp[2] = 2 + 0 = 2 。关键步骤 i=5 ：字符是 ')'，且 s[4] 也是 ')'，属于情况二。计算 j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2 。检查 s[2] ，它是 '('，匹配成功！所以 dp[5] = 2 + dp[4] + dp[1] = 2 + 2 + 2 = 6 。正确。算法步骤初始化一个长度与字符串相同的数组 dp ，所有值初始为 0。定义变量 maxLen 记录最终答案，初始为 0。从索引 i = 1 开始遍历字符串（因为 i=0 是单个字符，有效长度最多为0）。如果 s[i] == ')' ：情况一：如果 s[i-1] == '(' ，则 dp[i] = 2 + (dp[i-2] if i >= 2 else 0) 。情况二：如果 s[i-1] == ')' 且 i - dp[i-1] > 0 （确保 j 索引有效）且 s[i - dp[i-1] - 1] == '(' ，则 dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if (i - dp[i-1] - 2) >= 0 else 0) 。在每次计算完 dp[i] 后，更新 maxLen = max(maxLen, dp[i]) 。遍历结束后，返回 maxLen 。复杂度分析时间复杂度：O(n) ，其中 n 是字符串的长度，我们只需要遍历一次数组。空间复杂度：O(n) ，我们需要一个长度为 n 的 dp 数组。这个解法通过精细地分类讨论，利用动态规划记录了以每个位置结尾的有效长度，从而能够准确地计算出全局的最长有效括号子串。