Longest Valid Parentheses 题解

题目描述

即从只含有'('和')'的字符串s中找出最长有效子串sub(s),返回该子串的长度len。
如：s=")()())"",sub(s)="()()";len=4。

题解

对字符串进行遍历，遇到相邻配对的'('和')'则消去，并与此处存在的匹配子串(不存在即为空串)合并，并记录此处存在某个长度的匹配子串。并与已知最大长度比较，若大于则更新最大长度。类似于寻找无向图中最大匹配时建立交错树时的缩花操作。

例如s=")()())""。则有

1. left = 0,right = 1,len = 0.
2. s[left]=')'与s[right]='('. 不匹配,遍历下一个:left = 1,right = 2.
3. s[left]='('与s[right]=')'. 匹配,消去:left = 0,right = 3. 并记录s[0]处有一个长度为2的有效子串,更新最大长度len = 2.
4. s[left]=')'与s[right]='('. 不匹配,遍历下一个:left = 3,right = 4.
5. s[left]='('与s[right]=')'. 匹配,消去:left = 0,right = 5,并与之前s[0]处记录的长度为2的有效子串合并,更新最大长度len = 4.
6. s[left]=')'与s[right]=')'. 不匹配,遍历下一个:left = 5,right = 6. 到达字符串s末尾，结束。
7. 得到最长有效子串的长度为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;
    }
};

总结

主要应用了缩花思想。