leetcode全部题目答案

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路

复杂度

时间 O(N) 空间 O(N)

用Stack的方法本质上和Valid Parentheses是一样的，一个右括号能消去Stack顶上的一个左括号。不同的是，为了能够计算括号对的长度我们还需要记录括号们的下标。这样在弹出一个左括号后，我们可以根据当前坐标减去栈中上一个（也就是Pop过后的Top元素）的坐标来得到该有效括号对的长度。

public class Solution { public int longestValidParentheses(String s) { Stack<Integer> stk = new Stack<Integer>(); int maxLen = 0; for (int i = 0; i <= s.length() - 1; i++){ char c = s.charAt(i); if (c == '('){ stk.push(i); } else { if (!stk.isEmpty() && s.charAt(stk.peek()) == '('){ int curLen = 0; stk.pop(); if (stk.isEmpty()){ curLen = i + 1; } else { curLen = i - stk.peek(); } maxLen = Math.max(maxLen, curLen); } else { stk.push(i); } } } return maxLen; } } 也可用动态规划的思想，但是没太看明白

复杂度

时间 O(N) 空间 O(N)

思路

动态规划法将大问题化为小问题，我们不一定要一下子计算出整个字符串中最长括号对，我们可以先从后向前，一点一点计算。假设d[i]是从下标i开始到字符串结尾最长括号对长度，s[i]是字符串下标为i的括号。如果s[i-1]是左括号，如果i + d[i] + 1是右括号的话，那d[i-1] = d[i] + 1。如果不是则为0。如果s[i-1]是右括号，因为不可能有右括号开头的括号对，所以d[i-1] = 0。

代码

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