算法leetcode

力扣32-最长有效括号子串

字数统计: 897字   |   阅读时长: 4分
, , ,

摘要: 最长有效括号子串

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

我们之前了解过有效括号如何判定的问题，本文我们看一个进一步的问题：在字符串中找到最长有效括号子串，有两种方法，除了栈以外，还有动态规划方法也很经典。

题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

提示：

1
2
3
1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号

示例 1：
输入：s = “()())()”
输出：[“(())()”,”()()()”]

示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,”(a)()()”]

示例 3：
输入：s = “)(“
输出：[“”]

题解

算法1：栈

在栈里保存 ( 对应的下标，遇到 ) 出栈时由下标差得长度。

首先压入 -1，对应子串以 s[0] 开头的情况。

遇到 ( 则压入当前下标 i。

遇到 ) 则弹出栈顶，用当前下标 i 和弹出后的栈顶下标得到当前子串长度。此时若栈空，则将 i 再压入，对应子串以 s[i + 1] 开头的情况。

题解 (C++)

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
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) 
            return 0;
        int n = s.size();
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == '(')
                st.push(i);
            else
            {
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    ans = max(ans, i - st.top());
            }
        }
        return ans;
    }
};

算法2：用计数器代替栈

用 left, right 两个计数器：

  • 当 left = right 时算总和。
  • left < right 时清零

需要从左往右遍历一趟再从右往左遍历一趟，以应对 ()(() 这种 case。

题解 (C++)

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
56
57
58
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        int n = s.size();
        int ans = 0;

        // 从左往右
        int start = 0;
        int left_parentheres = 0;
        int right_parentheres = 0;
        while(start < n)
        {
            if(s[start] == '(')
                ++left_parentheres;
            else
            {
                ++right_parentheres;
                if(left_parentheres == right_parentheres)
                {
                    ans = max(ans, left_parentheres + right_parentheres);
                }
                else if(left_parentheres < right_parentheres)
                {
                    left_parentheres = 0;
                    right_parentheres = 0;
                }
            }
            ++start;
        }

        // 从右往左
        start = n - 1;
        left_parentheres = 0;
        right_parentheres = 0;
        while(start >= 0)
        {
            if(s[start] == ')')
                ++right_parentheres;
            else
            {
                ++left_parentheres;
                if(left_parentheres == right_parentheres)
                {
                    ans = max(ans, left_parentheres + right_parentheres);
                }
                else if(left_parentheres > right_parentheres)
                {
                    left_parentheres = 0;
                    right_parentheres = 0;
                }
            }
            --start;
        }
        return ans;
    }
};

算法3：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义：
dp[i] := 以 i 结尾的最长有效长度

初始化：
dp[0..1] = 0
若 s[0] == '(' && s[1] == ')' 则令 dp[1] = 2

答案：
max(dp[i])

状态转移：
只更新 s[i] = ')' 的情况，s[i] = '(', dp[i] = 0
s[i] = ')' 有两种情况
1. '()' s[i] = ')' s[i - 1] = '(' dp[i] = dp[i - 2] + 2
2. '))' s[i] = ')' s[i - 1] = ')' dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

题解 (C++)

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
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if(n <= 1) 
            return 0;
        vector<int> dp(n, 0);
        if(s[0] == '(' && s[1] == ')') 
            dp[1] = 2;
        int ans = dp[0];
        for(int i = 2; i < n; ++i)
        {
            if(s[i] == ')')
            {
                if(s[i - 1] == '(')
                    dp[i] = dp[i - 2] + 2;
                else
                {
                    if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
                    {
                        dp[i] = dp[i - 1] + 2;
                        if(i - dp[i - 1] - 2 >= 0)
                            dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
Share