題目描述:
給定一個隻包含 ‘(’ 和 ‘)’ 的字元串,找出最長的包含有效括号的子串的長度。
示例 1:
輸入: “(()”
輸出: 2
解釋: 最長有效括号子串為 “()”
示例 2:
輸入: “)()())”
輸出: 4
解釋: 最長有效括号子串為 “()()”
class Solution {
public:
int longestValidParentheses(string s) {
//dp[i]:到i字元(含)為止,有效的字元長度
if(s.size()<2)
return 0;
int n=s.size();
vector<int> dp(n,0);
int max_len=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]-1>=0&&s[i-1-dp[i-1]]=='('){//下标不越界并且子數組對應的括号是'('
dp[i]=dp[i-1]+2+(i-dp[i-1]-1>0?dp[i-2-dp[i-1]]:0);
}
}
max_len=max(max_len,dp[i]);
}
return max_len;
}
};