最长有效括号

Category	Difficulty	Likes	Dislikes
algorithms	Hard (29.67%)	543	-

Tags

string | dynamic-programming

Companies

Unknown

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

Discussion | Solution

解法

动态规划

重点是把括号匹配的关系理清楚：

(在前，)在后
如果 (和 )之间是 (...)且 (...)是有效括号序列，那么 ...一定由 0 到多个不定长度的有效括号序列组成

理清括号匹配的关系后，再思考怎么用 dp 去套。。。

可以用 dp[i][j] == true来表示 [i, j]是有效括号序列，但实际上不用二维数组，一维就够了，dp[i][j] == true记录了两个信息

i到 j的长度，即 j - i + 1
i到 j之间，符合有效括号序列

这两个信息，用一维数组即可记录，dp[i] = n，表示以 i为结尾的长为 n的有效括号序列。那么当碰到某个字符是 )的时候，需要找到与之匹配且没有被匹配的 (：

dp[i - 1]记录的就是以 i为结尾的长为 n的最长有效括号序列
i - dp[i - 1] - 1就是与之匹配且没有被匹配的 (所在的位置

所以长度就是：dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 设 f[i]: 以s[i]为尾的最长有效括号长度, 题目转化为 max(f[i]) (i=0..n-1)。
    /// 则 f[i-1]: 以s[i-1]为尾的最长有效括号长度，对于f[i], 有如下关系:
    /// 1. 如果s[i]是'('，则以其为结尾不是有效括号，因此 f[i] = 0;
    /// 2. 如果s[i]是')'，以s[i-1]为尾的最长有效括号字符串为s[i-f[i-1]:i]。
    ///   示意图：
    ///         pre_index
    ///             |
    ///             v| f[i-1] |
    ///         *****(********))
    ///              ^        ^
    ///           i-f[i-1]  (i-1)
    ///   其前一个字符为s[i-f[i-1]-1], 记 pre_index=i-f[i-1]-1
    ///   - 如果s[pre_index]为'(', 则s[pre_index:i+1]也为有效括号串, 即:
    ///           f[i] = f[i-1] + 2
    ///   示意图：  ******((********))
    ///                  ^          ^
    ///             pre_index       i
    ///   - 此时，如果pre_index前仍然存在字符串，则最长有效长度还加上前面部分的有效长度，
    ///   使前后连贯起来, 因此：
    ///             f[i] += f[pre_index-1]
    ///                      f[i-1]
    ///   示意图           |<------->|i
    ///          ***(***)(**********)
    ///   f[pre_index-1] ^
    ///               pre_index
    pub fn longest_valid_parentheses(s: String) -> i32 {
        // 长度<2的不存在
        if s.len() < 2 {
            return 0;
        }
        let mut f = vec![0; s.len()];   //f[i]: 以s[i]结尾的最长有效括号长度
        for i in 1..s.len() {
            if s.chars().nth(i) == Some( ')' ) {
                let pre_index = i as i32 - f[i-1] - 1; //跳过以s[i-1]为结尾大最长有效括号
                if pre_index >=0 && s.chars().nth(pre_index as usize) == Some('(') {
                    f[i] = f[i-1] + 2;
                    if pre_index > 0 {
                        f[i] += f[(pre_index as usize)-1];
                    }
                }
            }
        }

        *f.iter().max().unwrap()
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        vector<int> dp(s.length(), 0);
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == ')') {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s[j] == '(')
                    dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

最长有效括号

最长有效括号

解法

动态规划

相关文章：