Leetcode32-最长有效括号深度解析
目录
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; // 内部有效长度 + 2 if (i-dp[i-1]-2 >=0) { dp[i] += dp[i-dp[i-1]-2]; // 前面独立结构的有效长度 } }关键点 ：
i-dp[i-1]-1是当前)对应的(的位置。dp[i-1]是内部嵌套的有效长度（如()的长度）。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;
}
}