欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > IT业 > Leetcode32 最长有效括号深度解析

Leetcode32 最长有效括号深度解析

2025/3/17 15:27:19 来源:https://blog.csdn.net/m0_73762612/article/details/146293191  浏览:    关键词:Leetcode32 最长有效括号深度解析

问题描述

找出字符串s中最长的有效括号子串的长度。

核心思路

  • 动态规划:定义dp[i]为以字符s[i]结尾的最长有效括号子串长度。
  • 分情况讨论:根据当前字符是否为)以及前面的字符情况,推导状态转移方程。

状态转移方程详解

Case 1:当前字符)与前一个字符(直接匹配
  • 场景:形如...()的结构。

  • 转移方程

    if (s.charAt(i-1) == '(') {dp[i] = dp[i-2] + 2;  // 前i-2个字符的有效长度 + 2
    }
    
  • 示例

    • s = "()",当i=1时,dp[1] = dp[-1] (视为0) + 2 = 2
Case 2:当前字符)与嵌套结构匹配
  • 场景:形如...((...))的结构。

  • 转移方程

    else if (i-dp[i-1]-1 >=0 && s.charAt(i-dp[i-1]-1) == '(') {dp[i] = dp[i-1] + 2;  // 内部有效长度 + 2if (i-dp[i-1]-2 >=0) {dp[i] += dp[i-dp[i-1]-2];  // 前面独立结构的有效长度}
    }
    
  • 关键点

    1. i-dp[i-1]-1是当前)对应的(的位置。
    2. dp[i-1]是内部嵌套的有效长度(如()的长度)。
    3. dp[i-dp[i-1]-2]是嵌套结构前面的独立有效长度(如()((...))中前面的())。
  • 示例

    • s = "(()())",当i=5时:
  • dp[4] = 4(对应内部()())。

  • i-dp[i-1]-1 =5-4-1=0,检查s[0](

  • dp[5] = 4 + 2 + dp[0] (视为0) = 6


完整代码分析

class Solution {public int longestValidParentheses(String s) {int maxLen = 0;int len = s.length();int[] dp = new int[len];for (int i = 1; i < len; i++) {if (s.charAt(i) == ')') {// Case 1:直接匹配前一个'('if (s.charAt(i-1) == '(') {dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;} // Case 2:嵌套匹配前面的'('else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {dp[i] = dp[i-1] + 2;if (i - dp[i-1] - 2 >= 0) {dp[i] += dp[i - dp[i-1] - 2];}}maxLen = Math.max(maxLen, dp[i]);}}return maxLen;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词