class Solution {
public:
bool validParenthesis(string s){
if (s.front() == ')' || s.back() == '(') return false;
stack<char> buff;
for (size_t i = 0; i < s.size(); i++){
if (!buff.empty() && (buff.top() == '(' && s[i] == ')') )
buff.pop();
else buff.push(s[i]);
}
return buff.empty();
}
int longestValidParentheses(string s) {
// base cases
if (s.empty() || s.size() == 1) return 0;
else if (s.size() == 2 && s == "()") return 2;
else if (s.size() == 2) return 0;
// begin recursion
size_t left = 0, right = s.size()-1;
while(s[left] != '(' && left < s.size()) left++;
while(s[right] != ')' && right > 0) right--;
if (left >= right) return 0;
else {
size_t length = right - left + 1;
string sub = s.substr(left, length);
if (validParenthesis(sub)) return length;
else {
string candidate1 = s.substr(left, length-1);
string candidate2 = s.substr(left+1, length-1);
string candidate3 = s.substr(left+1, length-2);
int res1 = longestValidParentheses(candidate1);
int res2 = longestValidParentheses(candidate2);
int res3 = longestValidParentheses(candidate3);
int maxLen = res1 > res2 ? res1 : res2;
return maxLen > res3? maxLen : res3;
}
}
}
};();
}
int longestValidParentheses(string s) {
// base cases
if (s.empty() || s.size == 1) return 0;
else if (s.size() == 2 && s == "()") return 2;
else if (s.size() == 2) return 0;
// begin recursion
size_t left = 0, right = s.size()-1;
while(s[left] != '(') left++;
while(s[right] != ')') right++;
if (left >= right) return 0;
else {
size_t length = right - left + 1;
string sub = s.substr(left, length);
if (validParenthesis(sub)) return length;
else {
string candidate1 = s.substr(left, length-1);
string candidate2 = s.substr(left+1, length-1);
string candidate3 = s.substr(left+1, length-2);
int res1 = longestValidParenthesis(candidate1);
int res2 = longestValidParenthesis(candidate2);
int res3 = longestValidParenthesis(candidate3);
int maxLen = res1 > res2 ? res1 : res2;
return maxLen > res3? maxLen : res3;
}
}
}
};
Brute force solution
TLE.
Grammar error: 1. when increasing left and right, should use ++ and -- respectively. Also note the boundaries.
2. When examining valid parentheses, note the pop and push... push should be only in the "else" statement.
TLE.
Grammar error: 1. when increasing left and right, should use ++ and -- respectively. Also note the boundaries.
2. When examining valid parentheses, note the pop and push... push should be only in the "else" statement.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.