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.**Understand the problem:**

The problem asks for finding the length of the longest valid parentheses substring. Note that it is substring not subsequence.

**Solution 1: Using DP**

For those kinds of "longest substring" problems, it is usually to use DP solution. This problem is kind of special using the DP solution.

1. Define dp[n], whereas dp[i] means the length of the longest valid parentheses substrings STARTING FROM i to str.length() - 1.

2. Transit function.

-- If the str[i] = ')', dp[i] = 0, because there will no well-formed parentheses starting from ')'.

-- If the str[i] = '(', we check dp[i + 1], the longest valid parentheses starting from i + 1, and jump to the index j = i + dp[i + 1] + 1. e.g.

( ( ) ( ) )

i j

So if j is within the length of the string and str[j] == ')', dp[i] = dp[i + 1] + 2. In addition, dp[i] += dp[j + 1], because what if after j the parentheses are still valid.

3. Initial state: dp[n - 1] = 0

4. Final state: It is quite special here. We cannot check dp[0] because dp[i] stands for the length of longest valid parentheses starting from i. So the longest substring may not starts from str[0]. As a result, we must check if dp[i] is the largest. So the final state is max(dp[i]).

**Code (Java):**

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

**Solution 2: Using a stack**

public class Solution { public int longestValidParentheses(String s) { if (s == null || s.length() < 2) { return 0; } Stack<Integer> stack = new Stack<Integer>(); int max = 0; int start = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { if (stack.isEmpty()) { start = i + 1; } else { stack.pop(); if (stack.isEmpty()) { max = Math.max(max, i - start + 1); } else { max = Math.max(max, i - stack.peek()); } } } } return max; } }

## No comments:

## Post a Comment