Shulou(Shulou.com)05/31 Report--

Today Xiaobian to share with you how C++ to achieve the longest effective parenthesis related knowledge points, detailed content, clear logic, I believe most people still know too much about this knowledge, so share this article for everyone to refer to, I hope you read this article after some harvest, let's learn about it together.

Longest Valid Parentheses

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

Example 1:

Input: "(()"

Output: 2

Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"

Output: 4

Explanation: The longest valid parentheses substring is "()()"

This is more difficult to find the longest valid parenthesis than the previous Valid parenthesis. Here, we still use the stack to solve it. We need to define a start variable to record the starting position of the legal parenthesis string. Traverse the string. If we encounter a left parenthesis, we will push the current subscript into the stack. If we encounter a right parenthesis, if the current stack is empty, we will record the next coordinate position to start. If the stack is not empty, we will take out the top element of the stack. At this time, if the stack is empty, Then update the result and the larger value in i - start + 1, otherwise update the result and st.top the larger value in i - www.example.com (), see the code below:

Solution 1:

class Solution {public: int longestValidParentheses(string s) { int res = 0, start = 0, n = s.size(); stack st; for (int i = 0; i

< n; ++i) { if (s[i] == "(") st.push(i); else if (s[i] == ")") { if (st.empty()) start = i + 1; else { st.pop(); res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top()); } } } return res; }}; 还有一种利用动态规划 Dynamic Programming 的解法。这里使用一个一维 dp 数组，其中 dp[i] 表示以 s[i-1] 结尾的最长有效括号长度（注意这里没有对应 s[i]，是为了避免取 dp[i-1] 时越界从而让 dp 数组的长度加了1），s[i-1] 此时必须是有效括号的一部分，那么只要 dp[i] 为正数的话，说明 s[i-1] 一定是右括号，因为有效括号必须是闭合的。当括号有重合时，比如 "(())"，会出现多个右括号相连，此时更新最外边的右括号的 dp[i] 时是需要前一个右括号的值 dp[i-1]，因为假如 dp[i-1] 为正数，说明此位置往前 dp[i-1] 个字符组成的子串都是合法的子串，需要再看前面一个位置，假如是左括号，说明在 dp[i-1] 的基础上又增加了一个合法的括号，所以长度加上2。但此时还可能出现的情况是，前面的左括号前面还有合法括号，比如 "()(())"，此时更新最后面的右括号的时候，知道第二个右括号的 dp 值是2，那么最后一个右括号的 dp 值不仅是第二个括号的 dp 值再加2，还可以连到第一个右括号的 dp 值，整个最长的有效括号长度是6。所以在更新当前右括号的 dp 值时，首先要计算出第一个右括号的位置，通过 i-3-dp[i-1] 来获得，由于这里定义的 dp[i] 对应的是字符 s[i-1]，所以需要再加1，变成 j = i-2-dp[i-1]，这样若当前字符 s[i-1] 是左括号，或者j小于0（说明没有对应的左括号），或者 s[j] 是右括号，此时将 dp[i] 重置为0，否则就用 dp[i-1] + 2 + dp[j] 来更新 dp[i]。这里由于进行了 padding，可能对应关系会比较晕，大家可以自行带个例子一步一步执行，应该是不难理解的，参见代码如下： 解法二： class Solution {public: int longestValidParentheses(string s) { int res = 0, n = s.size(); vector dp(n + 1); for (int i = 1; i left) left = right = 0; } left = right = 0; for (int i = n - 1; i >

= 0; --i) { (s[i] == "(") ? ++left : ++right; if (left == right) res = max(res, 2 * left); else if (left > right) left = right = 0; } return res; }}; The above is "C++ how to achieve the longest valid brackets" all the content of this article, thank you for reading! I believe everyone has a great harvest after reading this article. Xiaobian will update different knowledge for everyone every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.