StarWalker

Where my heart will take me

0%

Leetcode032-Longest Valid Parentheses

Posted on Edited on In Views: Valine:
Solution Report of LeetCode Acceptted

Description

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

Example

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:
1
2
Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is ‘(‘, or ‘)’.

Solution

  • Time Complexity:
  • Space Complexity:

Solution 1: Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int longestValidParentheses(String s) {
        if (s.length() < 2) return 0;
        Stack<Integer> st = new Stack<>();
        int res = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == '('){
                st.push(i);
            }
            else{
                if (st.isEmpty()){
                    st.push(i);
                }
                else {
                    if (s.charAt(st.peek()) == '('){
                        st.pop();
                        res = Math.max(res, i - (st.isEmpty() ? -1 : st.peek()));
                    }
                    else{
                        st.push(i);
                    }
                }
            }
        }
        return res;
    }
}

Solution 2: DP

1
2
3
4
5
6
7
If s[i] is '(', set dp[i] to 0,because any string end with '(' cannot be a valid one.

Else if s[i] is ')'

     If s[i-1] is '(', dp[i] = dp[i-2] + 2

     Else if s[i-1] is ')' and s[i-dp[i-1]-1] == '(', dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestValidParentheses(String s) {
        if (s.length() < 2) return 0;
        int res = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i) == ')'){
                if (s.charAt(i - 1) == '('){
                    dp[i] = (i - 2) >= 0 ? dp[i - 2] + 2 : 2;
                }
                else{// if s[i-1] == ')', combine the previous length.
                    if (i - dp[i - 1] - 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);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            //else if s[i] == '(', skip it, because longest[i] must be 0
        }
        return res;
    }
}