Topic Overview:
Title link: Ask me to do the problem
Problem
1. Unpassable Violence Algorithms
_To be honest, the first thing I thought of was this method, but it would exceed the time limit.
_Its idea is simple, two-tier loops find each substring, and then use the stack to determine if each substring is a valid substring, which is simpler than the leetcode bracket because it only has'('and').
Code:
class Solution {
public:
int longestValidParentheses(string s)
{
if (s == "")
{
return 0;
}
int len = s.size();
int maxsize = 0;
for (int left = 0; left < len; left++)
{
for (int right = left + 1; right < len; right++)
{
int size = right - left + 1;
if (maxsize < size && isValidParentheses(s, left, right))
{
maxsize = size;
}
}
}
return maxsize;
}
bool isValidParentheses(const string& s, int left, int right)
{
stack<char> st;
int cur = left;
for (cur = left; cur <= right; cur++)
{
char tmp = s[cur];
if (tmp == '(')
{
st.push(tmp);
}
else if (tmp == ')')
{
if (st.empty())
{
return false;
}
else
{
st.pop();
}
}
}
if (st.empty())
{
return true;
}
else
{
return false;
}
}
};
Time Complexity:
O
(
n
3
)
O(n^3)
O(n3)
Spatial Complexity:
O
(
n
)
O(n)
O(n)
2. Dynamic Planning
_So it looks like a question related to the previous location and the previous location can be defined using dynamic programming (this is what White thinks).
d
p
[
i
]
dp[i]
dp[i] denotes as
s
[
i
]
s[i]
s[i] i s the length of the longest valid substring at the end, and our purpose i s to traverse through each location
d
p
[
i
]
dp[i]
The dp[i] is calculated and the maximum value is returned for each round.
_First, the end of a valid substring cannot be'('), so you can create a dp array with all of the
d
p
[
i
]
dp[i]
dp[i] all set to 0, then only process
s
[
i
]
=
=
′
)
′
s[i] == ')'
The position of s[i]==')'.
_Check its succession first
s
[
i
−
1
]
s[i-1]
What i s s[i_1]:
- If it's a successor
s
[
i
−
1
]
s[i - 1]
s[i_1] i s'('
_Then first it will match the preceding to form a pair of valid parentheses, and then look at the preceding element of its preceding s [ i − 2 ] s[i - 2] s[i_2], see i − 2 i - 2 Is i_2 out of bounds?
1.1 If i − 2 i-2 i_2 is not out of bounds, we ask d p [ i ] dp[i] When dp[i] d p [ i − 2 ] dp[i - 2] dp[i_2] must have been calculated, d p [ i − 2 ] dp[i - 2] dp[i_2] means i − 2 i-2 The i_2 position is the longest valid substring length at the end, obviously i i The longest valid substring length at position i is equal to 2 (it and s [ i − 1 ] s[i-1] s[i_1] matches to form a valid substring)+ i − 2 i-2 The i_2 position is the longest valid substring length at the end;
1.2 If i − 2 i-2 i_2 is out of bounds, there is no longest valid substring in front of it [ i − 1 , i ] [i - 1, i] [i_1,i] Linked, d p [ i ] dp[i] dp[i] directly equals 2. - If it's a successor
s
[
i
−
1
]
s[i -1]
s[i_1] i s')'
_First of all, in this case we have to look forward, first of all d p [ i − 1 ] dp[i - 1] dp[i_1] has been calculated and represents i − 1 i-1 i_1 position is the end of the longest substring length is d p [ i − 1 ] dp[i - 1] dp[i_1], we might as well connect this longest substring to the front of our string first, so that we can s [ i − 1 ] s[i-1] 's[i_1]') just matched off.
_Then go forward to find the position before the start of this substring i − 1 − d p [ i − 1 ] i - 1 - dp[i - 1] I_1_dp[i_1] (you can draw and walk by yourself), check if this location is out of bounds:
2.1 If it goes beyond the bounds, then we can't find'('to match s[i]), so don't deal with this situation d p [ i ] dp[i] dp[i], just keep the original value 0, indicating that there is no valid substring at the current position
2.2 If no bounds are exceeded, then check d p [ i − 1 − d p [ i − 1 ] ] = = ′ ( ′ dp[i - 1 - dp[i - 1]]== '(' Dp[i_1_dp[i_1]]=='('is true or not)
2.2.1 If true, the left bracket where s[i] should be matched i s found. Similarly, after checking to see if the previous position i s out of bounds, if it i s not out of bounds, the longest equal substring in front i s connected. If it i s out of bounds, the length of the substring i s only d p [ i − 1 ] dp[i - 1] dp[i_1] (previously connected i − 1 i-1 The longest equal substring of the i_1 position) and 2 (valid parentheses formed by matching this position to the I position)
$
dp[i] = dp[i - 1] + 2 + (i - 2 - dp[i - 1] >= 0 ? dp[i - 2 - dp[i - 1]]:0);
$
2.2.3 If not established, then no and i i If the i position matches the left bracket, is it possible that the string with both left brackets may have been removed in front, which is obviously impossible because we d p [ i − 1 ] dp[i - 1] dp[i_1] is looking for i − 1 i-1 i_1 is the longest equal substring at the end, if there is one ahead that can be eliminated i − 2 − d p [ i − 1 ] i - 2 -dp[i -1] The left parenthesis of the i_2_dp[i_1] position, that's with our d p [ i − 1 ] dp[i - 1] The value of dp[i_1] is contradictory, so in this case i i i position has no valid substring, d p [ i ] dp[i] dp[i] is best left untreated.
Code:
class Solution {
public:
int longestValidParentheses(string s)
{
//Dynamic programming method
//One-dimensional array dp denotes the longest valid bracket length ending with the current character
//Obviously all positions j,dp[j] ending with'('are equal to 0,
//Because a valid parenthesis end cannot be'('
//Then consider position I that ends with')', and judge s[i-1]
//1 If s[i-1]=='('
//Then the longest valid bracket length dp[i] ending at position I
//Is equal to dp[i] = 2 + (i-2 >= 0? Dp[i-2]: 0)
//Equivalent to s[i-1] and s[i] paired with valid brackets in front
//0 if the front crosses the line
//2 If s[i-1]==')'
//Then connect the longest valid bracket length dp[i - 1] of the previous position first
//This cancels out the')'of s[i-1]
//Then go forward I-1 to reach the previous position i-1-dp[i-1]
//The previous position to the leftmost of the valid bracket string ending with s[i - 1]
//Then see if this location is'('
//2.1 If that position cancels out the')'of s[i]
//Then check to see if the previous position of this location is out of bounds I - 2 - dp[i - 1] >= 0
//2.1.1 Connect this valid parenthesis ending at this position if it is not out of bounds
//That is, dp[i] = dp[i-1] + dp[i-2-dp[i-1]] + 2
//2.1.2 If that dp[i] is out of bounds with respect to dp[i - 1]
//Only')'of 2 s[i] and'(i - 1 - dp[i-1]] have been added
//dp[i] = dp[i - 1] + 2
//2.2 If that's not the case, matching fails
//The length of the longest substring ending at s[i] position should be 0
if (s == "")
{
return 0;
}
int maxlen = 0;
int len = s.size();
vector<int> dp(len, 0);
for (int i = 0; i < len; i++)
{
//s[i]=='(' doesn't matter if it's in the past
if (s[i] == ')')
{
if (i - 1 >= 0)
{
//If I-1 is less than 0, the first character is')'
//As long as dp[0] equals 0, else is fine
if (s[i - 1] == '(')
{
dp[i] = 2 + (i - 2 >= 0 ? dp[i - 2]: 0);
}
else if (s[i - 1] == ')')
{
if (i - 1 - dp[i - 1] >= 0
&& s[i - 1 - dp[i - 1]] == '(')
{
//Equally out of bounds or not equal to')'
//You won't find a match'('for s[i]
//Natural dp[i] = 0
//Leave the else case unattended
dp[i] = dp[i - 1]
+ (i - 2 - dp[i - 1] >= 0 ?
dp[i - 2 - dp[i - 1]] : 0) + 2;
//If not connected
//If it crosses the border, it doesn't matter
}
}
}
}
if (dp[i] > maxlen)
{
maxlen = dp[i];
}
}
return maxlen;
}
};
Time Complexity:
O
(
n
)
O(n)
O(n) (traversed string only once)
Spatial Complexity:
O
(
n
)
O(n)
O(n)(
d
p
dp
Space consumption of dp arrays)
3. Solve by using stack
_This method uses the left parenthesis of valid substrings to put them on the stack, and the right parenthesis to leave them on the stack, so we can always empty the stack. If we can put the starting position of valid substrings or the previous position of the starting position of valid substrings in the stack, then we can get the length of valid substrings of this round.
_So we stack the subscripts that did not get matched right parentheses at the end of the current moment, then encounter left parentheses on the stack, and encounter right parentheses on the stack, then
lower
one
round
Yes
effect
Include
Number
son
strand
Of
junction
tail
lower
mark
−
upper
one
individual
no
Yes
cover
Pi
match
Of
′
)
′
Of
lower
mark
=
c
u
r
s
i
z
e
The end subscript of the next valid bracket substring - the previous one not matched')'is = cursize
The end subscript of the next round of valid bracket substrings_the previous unmatched')'is cursize, and the previous unmatched')' subscript is the first position of the valid substring (').
_To control the boundary condition, we first press A-1 in, encounter left bracket in stack, encounter right bracket pop()
_If the back stack of pop() is empty, then you are the latest without matching right parentheses, putting your subscripts on the stack;
_If the stack behind pop() is not empty, then what remains in the stack is either the last unmatched right parenthesis or the last unmatched left parenthesis. In summary, the effective parenthesis length is equal to the current position subscript minus the last unmatched subscript, that is
c
u
r
s
i
z
e
=
i
−
s
t
.
t
o
p
(
)
;
cursize = i - st.top();
cursize=i_st.top();, Then take big turns.
Code:
class Solution {
public:
int longestValidParentheses(string s)
{
int size = s.size();
if (size == 0)
{
return 0;
}
//Stack behavior we know
//The correct valid bracket substring must empty the stack by stacking out
//Then if you put a subscript to the previous one that was not matched')'
//End subscript of next round of valid bracket substrings - previous one not matched')'
//= cursize
//Actually, the subscript for the last unmatched')'is
//The preceding position of'('at the beginning of this valid substring
//This cursize length is the length of this round of valid substrings
//And then each round is big enough
//Press A-1 in to the stack to ensure boundaries
stack<int> st;
st.push(-1);
int maxsize = 0;
for (int i = 0; i < size; i++)
{
if (s[i] == '(')
{
st.push(i);
}
else
{
//Right parenthesis pop s once on the stack
st.pop();
if (st.empty())
{
//If the stack is empty after pop
//That means the last unmatched right parenthesis was dropped by our pop
//Because the stack was not empty at first why there was -1
//So it needs to be updated to a new unmatched right parenthesis
//Its subscripts are stacked
st.push(i);
}
else
{
//If pop finishes stack not empty
//The right parenthesis subscript in the description stack that was not matched last time
//Or the subscript of the previous matching left parenthesis
//In both cases, let's calculate the current maximum effective length
int cursize = i - st.top();
if (cursize > maxsize)
{
maxsize = cursize;
}
}
}
}
return maxsize;
}
};
Time Complexity:
O
(
n
)
O(n)
O(n) (traversed string only once)
Spatial Complexity:
O
(
n
)
O(n)
O(n) (Stack consumption)
4. Solution by using the counter of left and right parentheses
_The step of this method is to run through the variables from left to right first, and counter if'(') is encountered
l
e
f
t
+
+
left++
left++; If')', counter
r
i
g
h
t
+
+
right++
Right++, and then check if right is greater than left. If it is greater than the right parenthesis of our string at this point, we cannot go forward to get the left parenthesis to match this right parenthesis. It is no longer a valid substring.
r
i
g
h
t
,
l
e
f
t
right,left
right,left returns to 0; Otherwise, check if right is equal to left, and if equality means that there is a valid substring at this time, the fire speed will make the largest equal substring it has ever passed by larger.
_Such a traversal will miss
l
e
f
t
>
r
i
g
h
t
left>right
Left>right can also have valid substrings, so we make up for this by traversing from end to end.
First put
l
e
f
t
,
r
i
g
h
t
left,right
left,right set to 0, then move forward from the end of the string, if'('), counter
l
e
f
t
+
+
left++
left++; If')', counter
r
i
g
h
t
+
+
right++
Right++, and then check if the left ft is greater than right. If it is more than the left parenthesis in the reverse direction, we cannot go forward to get the right parenthesis to match the left parenthesis, so it is no longer a valid substring.
l
e
f
t
,
r
i
g
h
t
left,right
left,right restored to 0; Otherwise, check if right is equal to left, and if equality means that there is a valid substring at this time, the fire speed will make the largest equal substring it has ever passed by larger.
_The process of moving backwards and forwards will be supplemented
l
e
f
t
>
r
i
g
h
t
left>right
The possible equal substring for left > right is that the left is equal before it is greater than right, and then it is judged to be equal. The left is greater than right, and immediately finds the next set of valid strings, but reverse traversal ignores them
r
i
g
h
t
>
l
e
f
t
right > left
The possible valid substrings for right>left, similarly, are compensated for by the forward walk above.
_The biggest advantage of this method is that its spatial complexity is
O
(
1
)
O(1)
O(1), time complexity is
O
(
n
)
O(n)
O(n), so to speak, is the most comprehensive and optimal algorithm for this problem.
class Solution {
public:
int longestValidParentheses(string s)
{
//Double counter method left right
//The cleverness of this method lies in its subtle control of "valid parentheses"
//When traversing from left to right is if'('left++)
//If')', right++.
//Then check if right > left
//Explain that this is an invalid bracket and we reset both right and left back to 0
//If left == right
//Indicates that this is a set of valid parentheses with a maximum length of 2 left
//The problem with this is that the () brackets of (() are ignored
//Valid parentheses that can also appear when left > right are ignored
//That's okay. Go back through again from the end to 0
//But this time if left > right left right set 0
//This will leave out valid brackets that can also appear when all right > left
//But it's okay to make up for that in the traversal above
if (s == "")
{
return 0;
}
int left = 0;
int right = 0;
int size = s.size();
int ret = 0;
for (int i = 0; i < size; i++)
{
if (s[i] == '(')
{
left++;
}
else
{
right++;
}
if (right > left)
{
//If there are many right parentheses thrown away
left = 0;
right = 0;
}
else if (left == right)
{
//A valid bracket appears when you want to wait
if (2 * left > ret)
{
ret = 2 * left;
}
}
}
//That discards valid brackets that may also appear in left > right
//You'll make up for this as you move backwards and forwards
left = 0;
right = 0;
for (int i = size - 1; i >= 0; i--)
{
if (s[i] == '(')
{
left++;
}
else
{
right++;
}
if (left > right)
{
//If there are many left parentheses thrown away
left = 0;
right = 0;
}
else if (left == right)
{
//A valid bracket appears when you want to wait
if (2 * left > ret)
{
ret = 2 * left;
}
}
}
return ret;
}
};