括号匹配的最大长度问题
字数 2214 2025-11-02 10:11:13

括号匹配的最大长度问题

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

有效括号字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

例如：

  • 输入: s = "(()"，输出: 2 （最长有效子串是 "()"）
  • 输入: s = ")()())"，输出: 4 （最长有效子串是 "()()"）
  • 输入: s = ""，输出: 0

解题思路
我们将使用动态规划来解决这个问题。动态规划的核心思想是利用一个数组 dp 来存储中间结果，其中 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。

详细步骤

步骤1：定义状态

  • 定义 dp[i] 为以字符 s[i] 结尾的最长有效括号子串的长度。
  • 我们的目标是找到整个 dp 数组中的最大值。

步骤2：分析基本情况

  • 对于 i=0（字符串的第一个字符）：
    • 如果 s[0] 是 '('，那么它无法形成一个有效的结束，所以 dp[0] = 0。
    • 如果 s[0] 是 ')'，同样无法形成有效结束，dp[0] = 0。
  • 实际上，任何以 '(' 结尾的子串都不可能形成有效括号子串的结尾，因为有效子串必须以 ')' 结尾。所以，当我们遇到 '(' 时，可以直接设置 dp[i] = 0。

步骤3：状态转移方程（核心）
我们只关心 s[i] = ')' 的情况，因为只有这时才可能形成有效结尾。

情况1：前一个字符是 '('，即 s[i-1] = '('。

  • 形如 "...()"。
  • 那么，dp[i] 至少为 2，因为它和前面的 '(' 形成了一对。
  • 此外，我们还可以加上在这对括号之前已经形成的有效长度，即 dp[i-2]（如果 i-2 >= 0）。
  • 所以，状态转移方程为：dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)

情况2：前一个字符是 ')'，即 s[i-1] = ')'。

  • 形如 "...))"。
  • 这表示我们可能遇到嵌套的情况，比如 "((...))"。
  • 设当前索引为 i，那么以 s[i] 结尾的有效子串可能包含一个更早的 '(' 与之匹配。
  • 这个匹配的 '(' 的位置应该是 j = i - dp[i-1] - 1。
    • dp[i-1] 是以 s[i-1] 结尾的有效长度，我们跳过这个长度，再往前看一个字符。
  • 如果 j >=0 且 s[j] == '('，那么 s[j] 和 s[i] 可以匹配成功。
  • 匹配成功后，dp[i] 至少为 dp[i-1] + 2（新匹配的一对括号）。
  • 此外，在 s[j] 之前可能还有有效的括号子串，其长度为 dp[j-1]（如果 j-1 >=0）。
  • 所以，状态转移方程为：dp[i] = dp[i-1] + 2 + (dp[j-1] if j-1 >=0 else 0)，其中 j = i - dp[i-1] - 1。

步骤4：算法流程

  1. 初始化一个长度为 n（字符串长度）的数组 dp，所有元素设为 0。
  2. 初始化 max_len = 0。
  3. 从 i=1 开始遍历字符串（因为 i=0 时 dp[0] 肯定为 0）：
    a. 如果 s[i] == '('，则 dp[i] = 0。
    b. 如果 s[i] == ')'：
    1. 如果 s[i-1] == '('（情况1）：
      dp[i] = 2 + (dp[i-2] if i>=2 else 0)
    2. 如果 s[i-1] == ')'（情况2）：
      j = i - dp[i-1] - 1 // 找到可能与 s[i] 匹配的字符索引
      如果 j >=0 且 s[j] == '('：
      dp[i] = dp[i-1] + 2 + (dp[j-1] if j>=1 else 0)
      否则：
      dp[i] = 0
      c. 更新 max_len = max(max_len, dp[i])
  4. 返回 max_len。

步骤5：举例说明
以 s = ")()())" 为例：
索引: 0 1 2 3 4 5
字符: ) ( ) ( ) )
dp: [0,0,0,0,0,0]

  • i=1: s[1]='(' -> dp[1]=0
  • i=2: s[2]=')'，且 s[1]='(' -> 情况1
    dp[2] = 2 + dp[0] = 2 + 0 = 2
    max_len=2
  • i=3: s[3]='(' -> dp[3]=0
  • i=4: s[4]=')'，且 s[3]='(' -> 情况1
    dp[4] = 2 + dp[2] = 2 + 2 = 4
    max_len=4
  • i=5: s[5]=')'，且 s[4]=')' -> 情况2
    j = 5 - dp[4] - 1 = 5 - 4 - 1 = 0
    s[0] = ')'，不等于 '('，所以匹配失败，dp[5]=0

最终 max_len=4，符合预期。

总结
这个方法通过动态规划巧妙地记录了以每个位置结尾的最长有效括号长度，通过分类讨论两种情况，确保了所有可能的最长子串都被考虑到。时间复杂度为 O(n)，空间复杂度为 O(n)。

括号匹配的最大长度问题 题目描述 给定一个只包含 '(' 和 ')' 的字符串 s，找出其中最长的有效（格式正确的）括号子串的长度。 有效括号字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 例如： 输入: s = "(()"，输出: 2 （最长有效子串是 "()"） 输入: s = ")()())"，输出: 4 （最长有效子串是 "()()"） 输入: s = ""，输出: 0 解题思路 我们将使用动态规划来解决这个问题。动态规划的核心思想是利用一个数组 dp 来存储中间结果，其中 dp[ i ] 表示以第 i 个字符结尾的最长有效括号子串的长度。 详细步骤 步骤1：定义状态 定义 dp[ i] 为以字符 s[ i ] 结尾的最长有效括号子串的长度。 我们的目标是找到整个 dp 数组中的最大值。 步骤2：分析基本情况 对于 i=0（字符串的第一个字符）： 如果 s[ 0] 是 '('，那么它无法形成一个有效的结束，所以 dp[ 0 ] = 0。 如果 s[ 0] 是 ')'，同样无法形成有效结束，dp[ 0 ] = 0。 实际上，任何以 '(' 结尾的子串都不可能形成有效括号子串的结尾，因为有效子串必须以 ')' 结尾。所以，当我们遇到 '(' 时，可以直接设置 dp[ i ] = 0。 步骤3：状态转移方程（核心） 我们只关心 s[ i ] = ')' 的情况，因为只有这时才可能形成有效结尾。 情况1：前一个字符是 '('，即 s[ i-1 ] = '('。 形如 "...()"。 那么，dp[ i ] 至少为 2，因为它和前面的 '(' 形成了一对。 此外，我们还可以加上在这对括号之前已经形成的有效长度，即 dp[ i-2 ]（如果 i-2 >= 0）。 所以，状态转移方程为：dp[ i] = 2 + (dp[ i-2 ] if i-2 >= 0 else 0) 情况2：前一个字符是 ')'，即 s[ i-1 ] = ')'。 形如 "...))"。 这表示我们可能遇到嵌套的情况，比如 "((...))"。 设当前索引为 i，那么以 s[ i ] 结尾的有效子串可能包含一个更早的 '(' 与之匹配。 这个匹配的 '(' 的位置应该是 j = i - dp[ i-1 ] - 1。 dp[ i-1] 是以 s[ i-1 ] 结尾的有效长度，我们跳过这个长度，再往前看一个字符。 如果 j >=0 且 s[ j] == '('，那么 s[ j] 和 s[ i ] 可以匹配成功。 匹配成功后，dp[ i] 至少为 dp[ i-1 ] + 2（新匹配的一对括号）。 此外，在 s[ j] 之前可能还有有效的括号子串，其长度为 dp[ j-1 ]（如果 j-1 >=0）。 所以，状态转移方程为：dp[ i] = dp[ i-1] + 2 + (dp[ j-1] if j-1 >=0 else 0)，其中 j = i - dp[ i-1 ] - 1。 步骤4：算法流程 初始化一个长度为 n（字符串长度）的数组 dp，所有元素设为 0。 初始化 max_ len = 0。 从 i=1 开始遍历字符串（因为 i=0 时 dp[ 0 ] 肯定为 0）： a. 如果 s[ i] == '('，则 dp[ i ] = 0。 b. 如果 s[ i ] == ')'： 如果 s[ i-1 ] == '('（情况1）： dp[ i] = 2 + (dp[ i-2 ] if i>=2 else 0) 如果 s[ i-1 ] == ')'（情况2）： j = i - dp[ i-1] - 1 // 找到可能与 s[ i ] 匹配的字符索引 如果 j >=0 且 s[ j ] == '('： dp[ i] = dp[ i-1] + 2 + (dp[ j-1 ] if j>=1 else 0) 否则： dp[ i ] = 0 c. 更新 max_ len = max(max_ len, dp[ i ]) 返回 max_ len。 步骤5：举例说明 以 s = ")()())" 为例： 索引: 0 1 2 3 4 5 字符: ) ( ) ( ) ) dp: [ 0,0,0,0,0,0 ] i=1: s[ 1]='(' -> dp[ 1 ]=0 i=2: s[ 2]=')'，且 s[ 1 ]='(' -> 情况1 dp[ 2] = 2 + dp[ 0 ] = 2 + 0 = 2 max_ len=2 i=3: s[ 3]='(' -> dp[ 3 ]=0 i=4: s[ 4]=')'，且 s[ 3 ]='(' -> 情况1 dp[ 4] = 2 + dp[ 2 ] = 2 + 2 = 4 max_ len=4 i=5: s[ 5]=')'，且 s[ 4 ]=')' -> 情况2 j = 5 - dp[ 4 ] - 1 = 5 - 4 - 1 = 0 s[ 0] = ')'，不等于 '('，所以匹配失败，dp[ 5 ]=0 最终 max_ len=4，符合预期。 总结 这个方法通过动态规划巧妙地记录了以每个位置结尾的最长有效括号长度，通过分类讨论两种情况，确保了所有可能的最长子串都被考虑到。时间复杂度为 O(n)，空间复杂度为 O(n)。