Keshawn_lu's Blog

Leetcode 32. 最长有效括号

动态规划
字数统计: 447阅读时长: 2 min
2020/07/04 Share

题目简介：

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

示例 1:

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

示例 2:

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

思路：

利用动态规划的思想，dp[i]代表以s[i]为结尾的字符串的有效括号长度。

所以以(为结尾的是不会有有效括号长度的，dp[i] = 0。

以)为结尾的有两种情况

  1. s[i] = ')' && s[i - 1] = '('，此时dp[i] = dp[i - 2] + 2，即在之前的有效长度上+2。
  2. s[i] = s[i - 1] = ')'，此时需要判断s[i - dp[i - 1] - 1]是否等于(：
    • dp[i - 1]即前一个字符的有效长度，s[i - dp[i - 1] - 1]即是与s[i]相匹配的括号。
    • 若能匹配上，dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2，即前一个字符的有效长度加上与s[i - dp[i - 1] - 2]字符为结尾的有效长度(之前子串的有效长度)再加上2。

循环时存储长度的最大值，最后返回即可。

tip:

  • 需要注意边界问题，防止数组溢出。

代码如下：

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
class Solution {
public:
    int longestValidParentheses(string s) {

        if(s.empty())
            return 0;

        vector<int> dp(s.length(), 0);

        int max_len = 0;

        for(int i = 1; i < s.length(); i++){

            if(s[i] == ')' && s[i - 1] == '('){
                
                dp[i] = ((i - 2 >= 0) ? dp[i - 2] : dp[0]) + 2;
            }
            else if(s[i] == ')' && s[i - 1] == ')'){

                if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){

                    int pos = (i - dp[i - 1] - 2 >= 0) ? i - dp[i - 1] - 2 : 0;
                    dp[i] = dp[i - 1] + dp[pos] + 2;
                }
                    
            }
            max_len = max(max_len, dp[i]);
        }

        return max_len;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网