題目
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
分析
一開(kāi)始的思路是模擬。用模擬的做法主要的問(wèn)題是復(fù)雜，而且容易忽視一些邊界情況喳篇。在經(jīng)歷了N次的WA+修改之后懊烤，我的代碼終于AC了片林。我為我的這種精神感動(dòng)集漾。
總結(jié)一些這種做法的思路：
- 從左往右遍歷字符串
- 記錄每個(gè)合法子串開(kāi)始的位置
- 記錄尚未配對(duì)的"("的位置
- 記錄當(dāng)前合法子串的長(zhǎng)度
- 若合法子串結(jié)束合呐，取以下長(zhǎng)度的最大值：
1.出現(xiàn)")"且沒(méi)有尚未匹配的"("時(shí)码荔，取得當(dāng)前合法子串長(zhǎng)度漩勤；
2.字符串到達(dá)末尾感挥，取末尾位置與最后一個(gè)未匹配的"("之間的長(zhǎng)度，以及未匹配的"("兩兩之間的長(zhǎng)度越败，以及上一個(gè)合法子串串開(kāi)始的位置和最左側(cè)的未匹配"("之間的長(zhǎng)度触幼。
實(shí)現(xiàn)一
class Solution {
public:
int longestValidParentheses(string s) {
int ans=0, len=0, sl=s.size(), last=-1;
stack<int> stk;
for(int i=0; i<s.size(); i++){
if(s[i]=='('){
stk.push(i);
len++;
}
else if(!stk.empty()){
stk.pop();
len++;
}
else{
ans = max(ans, len);
len = 0;
last=i;
}
}
if(!stk.empty()){
int p = stk.top(), q=p;
stk.pop();
ans = max(ans, sl-p-1);
while(!stk.empty()){
q = stk.top();
ans = max(ans, p-q-1);
p = q;
stk.pop();
}
ans = max(ans, q-last-1);
}
else{
ans = max(ans, len);
}
return ans;
}
};
思考一
這題雖然這樣做出來(lái)了，但是感覺(jué)這種做法給自己帶來(lái)的提升不大究飞。一是真正面試的時(shí)候不會(huì)有這么多時(shí)間讓我想置谦，二是到時(shí)候也沒(méi)有機(jī)會(huì)讓我一次次地?cái)M合測(cè)試數(shù)據(jù)，三是這種做法有時(shí)候需要一拍腦袋得到亿傅，也挺看狀態(tài)和運(yùn)氣的媒峡。
看到題解中還有用dp的方法，所以從這個(gè)角度思考做法葵擎。我覺(jué)得dp主要問(wèn)題是尋找能夠具有無(wú)后效性的量谅阿，但是目前我還沒(méi)有找到什么有效方法，主要靠拍腦瓜酬滤，或者看答案=_=
這題中奔穿，我已開(kāi)始想選擇使用dp[i]代表s.substr(0, i)中的最大合法括號(hào)長(zhǎng)度，但很快發(fā)現(xiàn)需要很多補(bǔ)充條件敏晤。后來(lái)看了題解才知道dp[i]代表以s[i]為結(jié)尾的最大合法括號(hào)長(zhǎng)度比較好，因?yàn)樽铋L(zhǎng)子串的位置在這題里確實(shí)是很重要的因素缅茉。
實(shí)現(xiàn)二
class Solution {
public:
int longestValidParentheses(string s) {
int sl=s.size(), ans=0;
vector<int> dp(sl, 0);
for(int i=1; i<sl; i++){
int match = i - dp[i-1] -1;
if(s[i]==')' && match>=0 && s[match]=='('){
dp[i] = dp[i-1] + 2;
if(match>=1)
dp[i] += dp[match-1];
}
ans = max(ans, dp[i]);
}
return ans;
}
};
思考二
雖然這道題理解了嘴脾，但是如果要我自己想，我還是不知道怎么把這個(gè)想出來(lái)蔬墩。得繼續(xù)摸索要译打，看來(lái)未來(lái)很長(zhǎng)時(shí)間內(nèi)要繼續(xù)拍腦瓜了。
