題目
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
示例1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
示例2：
Input: ")()(()()())())"
Output: 12
Explanation: The longest valid parentheses substring is "()(()()())()"
問題分解
subproblem:每一個(gè)合法括號(hào)子串都是一個(gè)subproblem奕枢，計(jì)算每一個(gè)合法括號(hào)子串的長(zhǎng)度即可破喻。
guess:
'(' 到下一個(gè)點(diǎn)去拥坛，因?yàn)榭傆蟹椒苁乖?('屬于最長(zhǎng)合法括號(hào)里面。
')' 前面的是'('限煞，合法(一種情況)。前面的是')'，則看看前面還有等待結(jié)束的'('振劳，有的話就合法，沒有的不合法油狂。related:用個(gè)table記錄下合法子串開始位置到第i處之前的括號(hào)的狀況(subproblem)历恐。此外還要記錄最長(zhǎng)長(zhǎng)度，也就是每次不合法了专筷，就要刷新一次最長(zhǎng)長(zhǎng)度弱贼。
bottom up
solve the original problem
代碼實(shí)現(xiàn)
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.length();
if(len<1) return 0;
vector<int > table(len+1,0);//初始化一個(gè)table，初始值為0
int cnt = 0; //cnt就是計(jì)數(shù)用的磷蛹，記錄有多少個(gè)'('等待結(jié)束
if(s[0]=='(') cnt++;// cnt =1
else cnt --; //cnt=-1
int retMax = 0;
for(int i=1;i<len;i++){
if(s[i]=='('){
if(cnt<0) cnt=1;
else cnt++;
continue;
}
//為')'的情況吮旅。
cnt--;//一個(gè)'('被結(jié)束了，cnt-=1
if(cnt>=0){ //cnt>=0的話味咳，就說明前面都是合法的子串庇勃，<0的話在下一個(gè)i處會(huì)進(jìn)行cnt重置。
if(s[i-1]=='(') table[i+1] = table[i-1]+2;
else{
if(s[i-1-table[i]]=='(')
table[i+1] = table[i-1-table[i]]+2+table[i];//
}
if(retMax<table[i+1]) retMax = table[i+1];
}
}
return retMax;
}
};
