Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/32.html
32 Longest Valid Parentheses
Given a string containing just the characters '(' and ')',
find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
@tag-stack
Algorithm
To solve with the help of the stack, you need to define a start variable to record the starting position of the valid bracket string.
Traverse the string,
- if it encounters a left bracket, push the current index onto the stack,
- if it encounters a right bracket,
- if the current stack is empty, the next index position is recorded to be
start, - if the stack is not empty, the top element of the stack is taken out, at this time,
- if the stack is empty, update the result and the larger value of
i-start + 1, - otherwise update the result and
i-the greater valuein st.top()
- if the stack is empty, update the result and the larger value of
- if the current stack is empty, the next index position is recorded to be
Code
-
public class Longest_Valid_Parentheses { class Solution_noExtraSpace { public int longestValidParentheses(String s) { int res = 0, left = 0, right = 0, n = s.length(); // from left to right, '(()' => will never hit left==right for (int i = 0; i < n; ++i) { if (s.charAt(i) == '(') ++left; else ++right; if (left == right) res = Math.max(res, 2 * right); else if (right > left) left = right = 0; } // from right to left, '())' => will never hit left==right left = right = 0; for (int i = n - 1; i >= 0; --i) { if (s.charAt(i) == '(') ++left; else ++right; if (left == right) res = Math.max(res, 2 * left); else if (left > right) left = right = 0; } return res; } } class Solution_stack { public int longestValidParentheses(String s) { Stack<Integer> sk = new Stack<>(); int start = 0; int result = 0; for (int i = 0;i < s.length(); i++) { if(s.charAt(i) == '(') { sk.push(i); } else { if (sk.empty()) { start = i + 1; } else { sk.pop(); result = Math.max(result, sk.isEmpty() ? i - start + 1 : i - sk.peek()); } } } return result; } } // @note: scan direction: right pointer from start to end, left pointer from right pointer to start public class Solution_start_to_end { public int longestValidParentheses(String s) { if (s == null || s.length() == 0) { return 0; } int longest = 0; int j = 1; // this map will mark, from index=0 to position x, longest so far // 注意，这里是保证 s[i][j]是连续的valid，所以才可以用 "i = j - skipLeft - 1;"来找左边的 '(' int[] longestSoFar = new int[s.length()]; while(j < s.length()) { int skipLeft = longestSoFar[j - 1]; int i = j - skipLeft - 1; // to find left "(" // @note: I missed boundary check for i // if (s.charAt(i) == '(' && s.charAt(j) == ')') { if (i >= 0 && s.charAt(i) == '(' && s.charAt(j) == ')') { longestSoFar[j] = j - i + 1; // @note: or, longestSoFar[j - 1] += 2; // System.out.println(i + " " + j); // probe previous valid segement if (i - 1 >= 0 && longestSoFar[i - 1] > 0) { longestSoFar[j] += longestSoFar[i - 1]; } longest = Math.max(longest, longestSoFar[j]); } j++; } return longest; } } // @note: scan direction: left pointer from end to start, right pointer from left pointer to end public class Solution_end_to_start { public int longestValidParentheses(String s) { if (s == null || s.length() == 0) return 0; // 注意，这里是保证 s[i][j]是连续的valid，所以才可以用 "j = i + skip + 1;"来找右边的 '(' int[] dp = new int[s.length()]; int max = 0; // scan from end to start for (int i = s.length() - 2; i >= 0; i--) { // check how many to skip int skip = dp[i + 1]; int j = i + skip + 1; // @note: i missed boundray check for j if (j > s.length() - 1) { continue; } if (s.charAt(i) == '(' && s.charAt(j) == ')') { dp[i] = dp[i + 1] + 2; // check position after j, eg: ))((()))()()(( if (j + 1 < s.length() && dp[j + 1] > 0) dp[i] += dp[j + 1]; max = max > dp[i] ? max : dp[i]; } } return max; } } // @note: 2-d dp array, over time public int longestValidParentheses(String s) { if (s == null || s.length() == 0) { return 0; } int longest = Integer.MIN_VALUE; int j = 0; // marking, from i to j is valid parenthesis boolean[][] dp = new boolean[s.length()][s.length()]; // @note: eg. ")()())", need another map to record previous longest valid // this map will mark, at position x, longest so far int[] longestSoFar = new int[s.length()]; while(j < s.length()) { int i = 0; while(i <= j) { // check if valid if ((s.charAt(i) == '(' && s.charAt(j) == ')') && (j - i <= 1 || dp[i + 1][j - 1])) { dp[i][j] = true; // System.out.println(i + " " + j); // probe previous valid segement int prev = i > 0 ? longestSoFar[i - 1] : 0; // check longest longest = Math.max(longest, j - i + 1 + prev); // @note: record longest so far longestSoFar[j] = longest; } i++; } j++; } return longest; } } -
// OJ: https://leetcode.com/problems/longest-valid-parentheses/ // Time: O(N) // Space: O(N) class Solution { public: int longestValidParentheses(string s) { vector<int> dp(s.size() + 1, 0); int ans = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] == '(') continue; int start = i - dp[i] - 1; if (start >= 0 && s[start] == '(') dp[i + 1] = dp[i] + 2 + dp[start]; ans = max(ans, dp[i + 1]); } return ans; } }; -
class Solution: def longestValidParentheses(self, s: str) -> int: left = right = 0 res = 0 for c in s: if c == '(': left += 1 else: right += 1 if left == right: res = max(res, 2 * left) if left < right: left = right = 0 left = right = 0 # dont forget to reset for c in reversed(s): if c == '(': left += 1 else: right += 1 if left == right: res = max(res, 2 * left) if left > right: # reverse < to > left = right = 0 return res class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) if n < 2: return 0 dp = [0] * n for i in range(1, n): if s[i] == ')': if s[i - 1] == '(': dp[i] = 2 + (dp[i - 2] if i > 1 else 0) else: j = i - dp[i - 1] - 1 if j >= 0 and s[j] == '(': dp[i] = 2 + dp[i - 1] + (dp[j - 1] if j else 0) return max(dp) ############ class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ dp = [0 for _ in range(0, len(s))] left = 0 ans = 0 for i in range(0, len(s)): if s[i] == "(": left += 1 elif left > 0: left -= 1 dp[i] = dp[i - 1] + 2 j = i - dp[i] if j >= 0: dp[i] += dp[j] ans = max(ans, dp[i]) return ans