Java编程实战3：最长有效括号

最长有效括号

题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3

输入：s = “”
输出：0

提示

• 0 <= s.length <= 3 * 104s[i] 为 ‘(’ 或 ‘)’

解答

解题思路

定义 dp[i] 表示以下标为 i 的字符结尾的最长有效括号的长度，并将 dp 数组全部初始化为 0。由于有效的子串一定以 ‘)’ 结尾，只需求解 ‘)’ 在 dp 数组中对应位置的值，不会对以 ‘(’ 结尾的子串在 dp 数组中对应位置的值作修改，其值必定为 0。
从前往后遍历字符串求解 dp 值，每两个字符检查一次：
当 s[i]=‘)’ 且 s[i−1]=‘(’ 时，也就是字符串形如 “……()”，可以推出：
dp[i]=dp[i−2]+2
当 s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，可以推出： 如果 s[i−dp[i−1]−1]=‘(’，那么
dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
最后的答案即为 dp 数组中的最大值。

完整代码

class Solution {
    public int longestValidParentheses(String s) {        
    int res = 0;        
    int n = s.length();        
    int[] dp = new int[n];        
    for (int i = 1; i < n; ++i) {            
    if (s.charAt(i) == ')') {                
    if (s.charAt(i - 1) == '(') {                    
    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;                
    } 
    else if (i - dp[i - 1] > 0 && 
    s.charAt(i - dp[i - 1] - 1) == '(') 
    {                   
     dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;                
     }            
     }            
     res = Math.max(res, dp[i]);        
     }       
      return res;    
      }
      }