This is the 30th day of my participation in the wenwen Challenge

Topic describes

Given a string containing only ‘(‘ and ‘)’, find the length of the longest valid (well-formed and continuous) parenthesis substring.

Example 1:

Input: s = "(()" Output: 2 Explanation: The longest valid parenthesis substring is "()"Copy the code

Example 2:

Input: s = ")()())" Output: 4 Explanation: The longest valid parenthesis substring is "()()"Copy the code

Example 3:

Input: s = "output: 0Copy the code

Tip:

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

Their thinking

We define dp[I] to represent the length of the longest valid parenthesis ending with the subscript I character. We initialize the dp array to zero. Obviously a valid substring must end in ‘) ‘, so we know that the dp value of a substring ending in ‘(‘ must be 0. We just need to solve for the value of’) ‘at the corresponding position in the DP array.

We evaluate dp by traversing the string from front to back, checking every two characters:

S [I]= ‘) ‘and s[I −1]=’ (‘. “()”… “()”… () “, we can derive:

Dp [I] = dp [I] - 2 + 2

We can do this because the ending “()” is a valid substring and increases the length of the previously valid substring by 2.

S [I]= ‘) ‘and S [I −1]=’) ‘. ) “”… ) “”… ), we can come up with:

If s [I – dp/I – 1-1] = ‘(‘, so, dp [I] = dp [I – 1) + dp [I – dp/I – 1-2) + 2

We consider that if the penultimate ‘) ‘is part of a valid substring (called sub_s), and the last’) ‘, if it is part of a larger string, must have a corresponding ‘(‘, And it precedes the valid substring (that is, sub_s) in the penultimate ‘) ‘. Therefore, if the substring sub_s happens to be preceded by ‘(‘, then we update dp[I]\textit{dp}[I −1] dp[I] with 2 plus the length of subsSub_ssubs (dp[I −1]\textit{dp}[I −1]). We also add the length of the valid substring before the valid substring “(sub_s)”, that is, plus dp[I −dp[I −1]−2].

The final answer is the maximum in the dp array

code

C + + code

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0, n = s.length(a);vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ') ') {
                if (s[i - 1] = ='(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] = ='(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1> =])2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = max(maxans, dp[i]); }}returnmaxans; }};Copy the code