题解

题目描述

题解

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

例如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;    }};

总结

主要应用了缩花思想。