32. 最长有效括号 - LeetCode
两遍扫描
先从左往右扫描，记录未匹配的左括号数目
若等于0，则记录当前子串长度
若小于0，则匹配失败，将下一个位置作为子串起点
若大于0，则继续匹配
从右往左再进行一次相同的扫描，就可以考虑到左括号比右括号多的情况
因为从左往右扫描，左括号比右括号多的时候，会继续往右寻找右括号，而不是减少左括号
class Solution { public int longestValidParentheses(String s) { int len = s.length(); if(len == 0) return 0; int ans = 0; int i = 0, j = 0, num = 0; for(; j < len; j ){ if(s.charAt(j) == '(') num ; else{ if(num == 0) i = j 1; else { num--; if(num == 0) ans = Math.max(ans, j-i 1); } } } i = len - 1; j = len - 1; num = 0; for(;i >= 0; i--){ if(s.charAt(i) == ')') num ; else{ if(num == 0) j = i - 1; else { num--; if(num == 0) ans = Math.max(ans, j-i 1); } } } return ans; }}
时间复杂度为O(n)，空间复杂度为O(1)
动态规划
dp[i]表示以第i个字符结尾的最长有效括号长度，分情况讨论：
若s[i-1] == '('，则构成"...()"，dp[i] = dp[i-2] 2;
若s[i-1] == ')'，若要有效，必须构成"...((...))"，即s[i-dp[i-1]-1] == '('，此时dp[i] = dp[i-1] 2 dp[i-dp[i-1]-2]
s[i] == '('，dp[i] = 0
s[i] == ')'：
class Solution { public int longestValidParentheses(String s) { int len = s.length(); if(len == 0) return 0; int[] dp = new int[len]; int ans = 0; dp[0] = 0; for(int i = 1; i < len; i ){ if(s.charAt(i) == '(') dp[i] = 0; else if(s.charAt(i-1) == '(') dp[i] = 2 (i >= 2 ? dp[i-2] : 0); else if(i - dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') dp[i] = dp[i-1] 2 (i - dp[i-1] - 2 >= 0 ? dp[i-dp[i-1]-2] : 0); else dp[i] = 0; ans = Math.max(ans, dp[i]); } return ans; }}
时间复杂度为O(n)，空间复杂度为O(n)
赞 (0)