Leetcode32 longest valid bracket (dynamic programming difficult problem)

Give you one that only contains '('  and ')'  String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .

Example 1：

Input ：s = "(()"
Output ：2
explain ： The longest valid bracket substring is "()"
Example 2：

Input ：s = ")()())"
Output ：4
explain ： The longest valid bracket substring is "()()"
Example 3：

Input ：s = ""
Output ：0

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/longest-valid-parentheses

One ： Violence solution （ Easy to understand but with high time complexity ）

        The easiest way to think about this problem is to find the length of the longest valid bracket substring ending in each character in the string , When I think of this, I think of using dynamic programming , But the state transition equation of this problem is not well determined , I will write the solution of dynamic programming below . The simplest way to find the longest substring ending in each character is to solve it violently through the stack , The specific method is to traverse forward from the current character , Until it doesn't meet the conditions .

Here are a few things to pay attention to ：

1. Because this is traversal from back to front , So what is different from usual is that when you encounter the right parenthesis, it will be put on the stack , Stack when encountering the left bracket ;

2. How to determine the conditions for breaking the cycle ： When the stack is empty and the next character in the stack is ‘(' when ;

3. In the general question of judging whether it is valid , If the stack is not empty after traversal, it is directly determined that it is invalid , But this problem may happen ："))()", If you traverse forward from the last character , It is partly effective , So how to exclude the invalid part in the front . I set up a temp Variable , Except at the beginning, if the stack is empty, it indicates that there is already a set of valid parentheses , At this point through tmep To record its length . Then continue to traverse forward , Because there may be valid parentheses after it , When the stack is not empty at the end of traversal, it will return directly temp, That is, the previous valid part .

class Solution {
    public int longestValidParentheses(String s) {
        if (s.length() == 0) return 0;
        int ans = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            
        }
        return ans;
    }
    public int a (String s, int x) {
        Deque<Character> stack = new LinkedList<>();
        int res = 0;
        int temp = 0;
        for (int i = x; i >= 0; --i) {
            if (stack.isEmpty() && i != s.length() - 1 && s.charAt(i + 1) == '(') temp = res;
            if (stack.isEmpty() && s.charAt(i) == '(') break;
            else if (s.charAt(i) == ')') stack.addLast(s.charAt(i));
            else if (s.charAt(i) == '(') {
                stack.pollLast();
            }
            res++;
        }
        if(!stack.isEmpty()) return temp; 
        return res;
    }
}

Two ： Dynamic programming

The key of dynamic programming is to determine the state transition equation , The same idea as above requires the length of the longest valid bracket substring ending in each character in the string , And recorded in the array dp[] in , The idea is as follows ：

Traversal string

1. If the current character is '(' when , Cannot form a valid bracket substring that ends with the current character ;

2. If the current character is ')' when ：

        2.1 i-1 The character of the position is ’(', At this time, this character forms a valid bracket with the previous character , Directly to dp[i-2]+2 that will do , But consider i-2 Is it greater than 0;

        2.2 i-1 The character of the position is ')', At this point, if you want to form a valid string "..(.....))" The following conditions must be met ：

                1.dp[i - 1] Greater than 0, Because the middle of these two brackets must also be valid brackets , A set of parentheses outside a set of invalid parentheses is also invalid ;

                2.i - dp[i - 1] - 1 Greater than or equal to zero ,i - dp[i - 1] - 1 namely i The position of the corresponding left parenthesis ;

                3. The position of the corresponding left bracket should be '(' Otherwise, invalid parentheses ;

                4. After meeting the above conditions , It can be judged that dp[i] Greater than or equal to dp[i - 1] + 2, Because this may happen ："()(())", In this example, when dp[5]=2,dp[6]=6, This is because after connecting the left bracket of the corresponding position , If there are valid parentheses on the left of the left parenthesis, they should be counted together .

class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    if (i >= 2) dp[i] = dp[i - 2] + 2;
                    else dp[i] = 2;
                }else if (i - dp[i - 1] - 1>= 0 > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ans = ans > dp[i] ? ans : dp[i];
            }
        }
        return ans;
    }
}