首页 > 代码库 > Longest Valid Parentheses

Longest Valid Parentheses

2024-07-03 01:02:40   225人阅读

Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

也就是说要找到最长的子串满足匹配规则。

算法思路，建立两个数组pre[]和post[],生成规则如下：

pre数组：从前向后遍历原字符串s，若该下标i所对应的字符为‘(‘，则 ：(1)若i为0，pre[i]=1;(2)若pre[i-1]<0,pre[i]=1(3)其余情况，pre[i]=pre[i-1]+1;

post数组：从后向前遍历原字符串s，若该下标i所对应的字符为‘)‘，则：(1)若i为s.length-1，post[i]=1;(2)若post[i+1]<0,pre[i]=1(3)其余情况，pre[i]=pre[i+1]+1;

例如：字符串")()())"的pre数组为 -1  1  0  1  0  -1，post数组为2  1  2  1  2  1

然后在pre数组中从后向前找到第一个值为0的下标，若没有，则从pre数组中找出的最长子串为0，若找到，再向前找出第一个小于0的下标，或者全部大于0，此时下标递减到0，则从pre数组中找出的最长子串的长度就是这两个下标的差值。

同理，在post数组中从前向后找第一个值为0的下标，然后再找第一个值小于0的下标或者下标到s.length-1，从post数组中找到的子串长度即这两个下标的差值。

因此，满足条件的最长子串的长度就是从pre数组和post数组中找到的长度的最大值。

int pre[] = new int[s.length()];
        int post[] = new int[s.length()];
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ‘(‘) {
                if (i == 0) {
                    pre[i] = 1;
                } else {
                    if (pre[i - 1] < 0) {
                        pre[i] = 1;
                    } else {
                        pre[i] = pre[i - 1] + 1;
                    }
                }
            } else {
                if (i == 0) {
                    pre[i] = -1;
                } else {
                    pre[i] = pre[i - 1] - 1;
                }
            }
        }
        int pos = 0;
        pos = s.length();
        for (int i = s.length() - 1; i >= 0;) {
            while (pre[i] != 0) {
                i--;
                if (i < 0) {
                    break;
                }
            }
            pos=i;
            while (i>=0&&pre[i]>=0){
                i--;
            }
            start = (start>(pos-i))?start:(pos-i);
        }
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ‘)‘) {
                if (i == s.length() - 1) {
                    post[i] = 1;
                } else {
                    if (post[i + 1] < 0) {
                        post[i] = 1;
                    } else {
                        post[i] = post[i + 1] + 1;
                    }
                }
            } else {
                if (i == s.length() - 1) {
                    post[i] = -1;
                } else {
                    post[i] = post[i + 1] - 1;
                }
            }
        }
        
        pos = 0;
        for (int i = 0; i < s.length();) {
            while (post[i] != 0) {
                i++;
                if (i >= s.length()) {
                    break;
                }
            }
            pos=i;
            while (i<s.length()&&post[i]>=0){
                i++;
            }
            end = (end>(i-pos))?end:(i-pos);
        }
        return (start < end) ? end : start;

因为算法中遍历了两次原字符串，一次pre数组和一次post数组，因此时间复杂度为O(n)，空间复杂度为两个数组pre和post，为O(n)

////////////////////////////////////////////////////////////////////////////////////////////分割线/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

看了一下网上的做法，转载一下：

转自http://blog.csdn.net/cfc1243570631/article/details/9304525

这道题可以用一维动态规划逆向求解。假设输入括号表达式为String s，维护一个长度为s.length的一维数组dp[]，数组元素初始化为0。 dp[i]表示从s[i]到s[s.length - 1]包含s[i]的最长的有效匹配括号子串长度。则存在如下关系：

  • dp[s.length - 1] = 0;
  • i从n - 2 -> 0逆向求dp[]，并记录其最大值。若s[i] == ‘(‘，则在s中从i开始到s.length - 1计算dp[i]的值。这个计算分为两步，通过dp[i + 1]进行的（注意dp[i + 1]已经在上一步求解）：
    • 在s中寻找从i + 1开始的有效括号匹配子串长度，即dp[i + 1]，跳过这段有效的括号子串，查看下一个字符，其下标为j = i + 1 + dp[i + 1]。若j没有越界，并且s[j] == ‘)’，则s[i ... j]为有效括号匹配，dp[i] =dp[i + 1] + 2。
    • 在求得了s[i ... j]的有效匹配长度之后，若j + 1没有越界，则dp[i]的值还要加上从j + 1开始的最长有效匹配，即dp[j + 1]。


联系
我们