问题描述
找出字符串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]; // 前面独立结构的有效长度} }
-
关键点:
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;}
}