leetcode32. 最长有效括号

---

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”

示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

动态规划

dp[i]表示以第i个字符开头的括号，拥有的字符串长度，根据当前是左括号还是右括号，有不同的操作。注释在代码里。

class Solution { public int longestValidParentheses(String s) { if (s.length() == 0) return 0; int[] dp = new int[s.length()]; int max = 0; dp[s.length() - 1] = 0; for (int i = s.length() - 2; i >= 0; i--) {//从后往前遍历的 if (s.charAt(i) == ')') { //当前是右括号，如果他的右边是左括号，需要把左括号的状态传递过来 //比如(()()())(),最后dp应该是10,6，4,4,2,2，0,2，2,0。 //如果没有传递状态，最后是0,2，0,2，0,2，0,0，2,0 //这样会导致求出来的括号不是连续的，第一版代码就是这个问题，但是找不到代码了 if (s.charAt(i + 1) == '(') { dp[i] = dp[i + 1]; } else { dp[i] = 0; } } else { //当前是左括号 if (s.charAt(i + 1) == ')') { //如果右边是右括号，那么应该和下一个配对，并且把右括号的状态加上 dp[i] = 2 + dp[i + 1]; } else { //右边是左括号，那么可能是嵌套的情况 if (dp[i + 1] == 0) { //为0说明右边没有连续的括号 dp[i] = 0; } else { //计算和他对应的位置是否是右括号 int r = i + dp[i + 1] + 1; if (r < s.length() && s.charAt(r) == ')') { dp[i] = 2 + dp[i + 1] + dp[r]; //当前括号的长度2+右边连续的括号长度+和当前括号匹配的右括号的状态 } else { dp[i] = 0; } } } } max = Math.max(max,dp[i]); } //show(dp); return max; } public void show(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }

leetcode 116