地址：https://leetcode.com/problems/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 “()()”

理解：

寻找一个字符串中有效的括号

实现1：

基于动态规划的实现。

如果是一个有效的子串，一定以')'结束。因此，对于‘(’，保持0就可以了。

若s[i]==')'且s[i-1]==‘(’，则dp[i]=dp[i-2]+2;

若前面为')'，则需要通过dp[i-1]找到前面有效子串的起始，并判断更靠前一位是否是'('。并且，还要加上更靠前一位的已经有效子串的长度。

class Solution {

public:

int longestValidParentheses(string s) {

vector dp(s.length(),0);

int maxCnt = 0;

for (int i = 1; i < s.length(); ++i) {

if (s[i] == ')') {

if (s[i - 1] == '(')

dp[i] = i -2 >= 0 ? dp[i - 2] + 2 : 2;

else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {

dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);

}

maxCnt = max(maxCnt,dp[i]);

}

}

return maxCnt;

}

};

实现2：

从左到右和从右到左，将字符串遍历两次

class Solution {

public:

int longestValidParentheses(string s) {

int maxCnt = 0;

int left = 0,right = 0;

for (int i = 0; i < s.length(); ++i) {

if (s[i] == '(')

++left;

else

++right;

if (left == right)

maxCnt = max(maxCnt,2 * right);

else if (right >= left)

left = right = 0;

}

left = right = 0;

for (int i = s.length()-1; i >=0; --i) {

if (s[i] == '(')

++left;

else

++right;

if (left == right)

maxCnt = max(maxCnt,2 * left);

else if (left >= right)

left = right = 0;

}

return maxCnt;

}

};

实现3：

使用一个栈保留位置。

class Solution {

public:

int longestValidParentheses(string s) {

stack stk;

stk.push(-1);

int maxL=0;

for(int i=0;i

{

int t=stk.top();

if(t!=-1&&s[i]==')'&&s[t]=='(')

{

stk.pop();

maxL=max(maxL,i-stk.top());

}

else

stk.push(i);

}

return maxL;

}

};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!