Longest Valid Parentheses
文章目录
Longest Valid Parentheses 题解
题目描述
即从只含有'('和')'的字符串s中找出最长有效子串sub(s),返回该子串的长度len。
如:s=")()())"",sub(s)="()()";len=4。
题解
对字符串进行遍历,遇到相邻配对的'('和')'则消去,并与此处存在的匹配子串(不存在即为空串)合并,并记录此处存在某个长度的匹配子串。并与已知最大长度比较,若大于则更新最大长度。类似于寻找无向图中最大匹配时建立交错树时的缩花操作。
例如s=")()())""。则有
-
left = 0,right = 1,len = 0. -
s[left]=')'与s[right]='('. 不匹配,遍历下一个:left = 1,right = 2. -
s[left]='('与s[right]=')'. 匹配,消去:left = 0,right = 3. 并记录s[0]处有一个长度为2的有效子串,更新最大长度len = 2. -
s[left]=')'与s[right]='('. 不匹配,遍历下一个:left = 3,right = 4. -
s[left]='('与s[right]=')'. 匹配,消去:left = 0,right = 5,并与之前s[0]处记录的长度为2的有效子串合并,更新最大长度len = 4. -
s[left]=')'与s[right]=')'. 不匹配,遍历下一个:left = 5,right = 6. 到达字符串s末尾,结束。 - 得到最长有效子串的长度为
len = 4.
假设原字符串s长度为n,时间复杂度为O(n)。
代码
typedef int _Type;
class Solution {
public:
int longestValidParentheses(const std::string& s) {
_Type left = 0, longest = 0, len = s.size();
std::vector<_Type> vec(len);
for (_Type i = 0; i < len; ) {
if (s[i] == '(') {
vec[left++] = i++;
} else if (s[i++] == ')' && left > 0) {
_Type tmp = i - vec[--left];
if (tmp > longest)
longest = tmp;
if (i < len && s[i] == '(')
vec[left++] = i++ - tmp;
}
}
return longest;
}
};
总结
主要应用了缩花思想。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论