tag:blogger.com,1999:blog-8522573717713847738.post6904240779235730584..comments2024-03-28T00:14:29.070-07:00Comments on Yu's Coding Garden : leetcode Question 46: Longest Valid ParenthesesAnonymoushttp://www.blogger.com/profile/00263085222060621782noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8522573717713847738.post-6563925465563515272017-08-02T14:18:23.241-07:002017-08-02T14:18:23.241-07:00Had difficult time understanding the algo. So trie...Had difficult time understanding the algo. So tried something that made a bit more sense to me atleast. Here is my approach.<br /><br />//LongestValid-ParamSubstring.cpp : Defines the entry point for the console application.<br />//Basically the idea I have used is every time you see a opening bracket store its index.<br />//whenever you see a closing bracket, <br />//if the stack is empty -- that means we are seeing closing bracket first and it cannot be a valid string yet and skip it.<br />//if the stack is not empty -- means there was a opening bracket earlier. then compute the interval and store it in a vector if the vector is empty.<br />// -- if the interval vector is not empty means previously we had seen some valid paranthesis strings<br />// -- now find out how the newly found range overlaps with the previous found range<br />// -- if they overlap then delete the previous range result and modify and range and insert it<br />// -- if they don't overlap, then insert a new range and later on results can be added.<br /><br />#include "stdafx.h"<br />#include <br />#include <br />#include <br /><br />using namespace std;<br /><br />int LongestValidParan(string arr)<br />{<br /> if (arr.size() == 0)<br /> return 0;<br /> if (arr.size() == 1)<br /> return -1;<br /><br /> vector> result ;<br /> stack myStack;<br /> <br /> for (int i = 0; i < arr.size(); i++)<br /> {<br /> if (arr[i] == '(')<br /> myStack.push(i);<br /><br /> else if (arr[i] == ')')<br /> {<br /> if (myStack.empty())<br /> continue;<br /> else<br /> {<br /> int topIndex = myStack.top();<br /> myStack.pop();<br /> if (result.size() == 0)<br /> {<br /> result.push_back({ topIndex, i });<br /> }<br /> else<br /> {<br /> auto lastresultIndex = result.back();<br /> if ((lastresultIndex.first <= topIndex) && ( i <= lastresultIndex.second))<br /> continue;<br /> else if ((lastresultIndex.first <= topIndex) && ( topIndex <= lastresultIndex.second) && (i >= lastresultIndex.second))<br /> {<br /> result.pop_back();<br /> result.push_back({ lastresultIndex.first, i });<br /> }<br /> else if ((topIndex <= lastresultIndex.first ) && (i <= lastresultIndex.second)&& (lastresultIndex.first <=i))<br /> {<br /> result.pop_back();<br /> result.push_back({ topIndex ,lastresultIndex.second });<br /> }<br /> else if ((topIndex<= lastresultIndex.first ) && (lastresultIndex.second <= i))<br /> {<br /> result.pop_back();<br /> result.push_back({ topIndex,i });<br /> }<br /> else if ((lastresultIndex.second < topIndex) && (i > lastresultIndex.second))<br /> {<br /> result.push_back({ topIndex,i });<br /> }<br /> }<br /> }<br /> }<br /> }<br /> int resultlen = 0;<br /> for (auto a : result)<br /> {<br /> resultlen = resultlen + a.second - a.first + 1;<br /> }<br /> return resultlen;<br />}<br /><br /><br />int main()<br />{<br /> printf("\n%d", LongestValidParan({ "((()()"}));<br /> printf("\n%d", LongestValidParan({ "()()" }));<br /> printf("\n%d", LongestValidParan({ "(()()" }));<br /> printf("\n%d", LongestValidParan({ "()(()" }));<br /> printf("\n%d", LongestValidParan({ "()(()))))" }));<br /> printf("\n%d", LongestValidParan({ "((()))" }));<br /> printf("\n%d", LongestValidParan({ "))((()))" }));<br /> return 0;<br />}<br /><br />Anonymoushttps://www.blogger.com/profile/13058839884732295201noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-13170278691102608512015-01-08T12:53:35.754-08:002015-01-08T12:53:35.754-08:00This comment has been removed by the author.LoveIthttps://www.blogger.com/profile/03369330797763616665noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-57942775586398126602014-08-19T14:58:39.332-07:002014-08-19T14:58:39.332-07:00This comment has been removed by the author.showerhttps://www.blogger.com/profile/02742546831168974275noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-25231270740544491662014-06-27T18:08:01.086-07:002014-06-27T18:08:01.086-07:00You don't need to use variable t. My solution ...You don't need to use variable t. My solution passed the leetcode test.<br />int longestValidParentheses(string s) <br /> {<br /> stack> stack;<br /> int result = 0;<br /> for(int i=0; i < s.size(); i++)<br /> {<br /> if ((s[i] == '(') ||stack.empty())<br /> {<br /> stack.push(make_pair(s[i], i));<br /> }<br /> else<br /> {<br /> pair p = stack.top();<br /> if(p.first == ')')<br /> {<br /> stack.push(make_pair(s[i], i));<br /> }<br /> else<br /> {<br /> stack.pop();<br /> if (stack.empty())<br /> {<br /> int l = i +1;<br /> if (l > result)<br /> result = l;<br /> }<br /> else<br /> {<br /> pair t = stack.top();<br /> int l = i - t.second;<br /> if (l > result)<br /> result = l;<br /> }<br /> }<br /> }<br /> }<br /><br /> return result;<br /> }Anonymoushttps://www.blogger.com/profile/08983305950597904101noreply@blogger.com