32. Longest Valid Parentheses

Leetcode link

解题思路——DP

• TC：O(n)
• SC：O(n)

题目要求我们求出最长且可以左右配对的括号子字符串长度

求极值的问题可以用动态规划来解，我们需要一个一维数组 dp，dp[i] 表示以下标 i 字符结尾的最长有效括号子字符串长度

首先，以 ( 结尾的子串它的 dp 数组对应值肯定是 0

所以我们只需要判断以 ) 结尾的部分就好，总共有两种可能性：

• s[i-1] == '(' && s[i] == ')'：也就是最后两位是有效括号，这个时候 dp[i] = dp[i - 2] + 2
• s[i-1] == ')' && s[i] == ')'：也就是最后两位都是右括号，这个时候需要往左边找第一个未匹配的左括号
  • 如果 s[i - dp[i - 1] - 1] == '(' 成立的话，我们可以推导出这种情况的状态转移方程为
  • dp[i] = dp[i - 1] + 2 + dp[i - d[i - 1] - 2]

举个例子：有个字符串 () ( () )

1. 首先建立一个数组 dp，初始化为 0
2. 遍历字符串，找出上述两种情况
3. 当 i == 1，为第一种情况，用 dp[i] = dp[i - 2] + 2 更新 dp
4. 当 i == 4 ，为第一种情况，用 dp[i] = dp[i - 2] + 2 更新 dp
5. 当 i == 5，为第二种情况，这个时候找到最近为匹配左括号的方法是，用自己的下标减去左边 dp 数组的匹配数量，再减去 1
6. 如果有找到，则 i == 2 到 i == 5 这一段的 dp 可以用dp[i] = dp[i - 2] + 2 来更新
7. 但是考虑到之前也有可能出现匹配的子串，比如这里的 s[0] 跟 s[1]，所以需要加上 dp[i - d[i - 1] - 2]，也就是 dp[1] 的值

C++

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(), 0);
        int res = 0;
        for(int i = 1;i<s.size();i++) {
            if(s[i] == ')') {
                if(s[i-1] == '(') {
                      // ...() 的情况，记得判断数组下标边界
                    dp[i] = (i>=2 ? dp[i-2] : 0) + 2;
                } else if((i-dp[i-1]-1 >= 0) && (s[i - dp[i - 1] - 1] == '(')) {
                    // ...)) 的情况，除了要判断最后的有效子串长度还要加上前面的子串
                    dp[i] = dp[i-1] + 2 + ((i - 2 - dp[i - 1] >=0) ? dp[i - 2 - dp[i - 1]] : 0);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

Javascript

var longestValidParentheses = function(s) {
    let res = 0;
    let dp = new Array(s.length).fill(0);
    for(let i=1;i<s.length;i++) {
        if(s[i] === ')') {
            if(s[i-1] === '(') {
                dp[i] = (i>=2 ? dp[i-2] : 0) + 2;
            } else if((i-1-dp[i-1] >= 0) && s[i-1-dp[i-1]] === '(') {
                dp[i] = dp[i-1] + 2 + (i-dp[i-1]>=2 ? dp[i-dp[i-1] - 2] : 0);
            }
        }
        res = Math.max(dp[i], res);
    }
    return res;
};

解题思路——双向遍历

• TC: O(n)
• SC: O(1)

还有另一种方法是双向遍历，首先我们先考虑一种方法：用两个计数器 left 跟 right 分别计算左括号跟右括号出现的次数

具体步骤如下：

• 从左往右遍历字符串
• 如果遇到左括号，left++；如果遇到右括号，right++
• 当 left == right 的时候，表示当前遍历的字符串是有效的，保存结果
• 当 right > left 的时候，表示右括号大于左括号，而单独的右括号不能组成有效字符串，所以重置 left = right = 0

上述步骤可以处理大部分的问题，但是还有一种组合会被忽略：(()

所以我们需要从右往左再遍历一次，只是这次重置条件就变成 left > right了

C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        int left = 0, right = 0;

        for(int i=0;i<s.size();i++) {
            if(s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if(left == right) {
                res = max(res, right * 2);
            }
            if(right > left) {
                left = right = 0;
            }
        }
        left = right = 0;

        for(int i = s.size()-1;i>=0;i--) {
            if(s[i] == '(') {
                left++;
            }else {
                right++;
            }

            if(left == right) {
                res = max(res, right * 2);
            }
            if(left > right) {
                left = right = 0;
            }
        }
        return res;
    }
};

Javascript

var longestValidParentheses = function(s) {
    let right = 0, left = 0, res = 0;
    for(let i=0;i<s.length;i++) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }
        if(left === right) {
            res = Math.max(res, 2 * right);
        } else if(right > left) {
            right = left = 0;
        }
    }
    right = left = 0;
    for(let i = s.length-1;i>=0;i--) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }
        if(left === right) {
            res = Math.max(res, 2 * right);
        } else if(left > right) {
            right = left = 0;
        }
    }

    return res;
};