最长有效括号题解

目录

  1. 题目：最长有效括号
  2. 算法：动态规划
    1. 解法：
    2. 状态转移方程
    3. 时间复杂度&空间复杂度
  3. LeetCode执行结果
  4. 感受
  5. 代码

题目：最长有效括号

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣(LeetCode)

算法：动态规划

解法：

定义 表示以第i个字符结尾的字符串中最长的有效括号长度。

example1:

1
2
3
string: "()()()"
index  : 0 1 2 3 4 5
dp:      0 2 0 4 0 6

example2:

1
2
3
string: "()((())"
index  : 0 1 2 3 4 5 6 
dp:      0 2 0 0 0 2 4

example3:

1
2
3
string: "()(())"
index: 0 1 2 3 4 5
dp:    0 2 0 0 2 6
  1. 若, 由于(不可能是有效括号的结束字符，所以。
  2. 若，存在多种情况
    • 若为， 若是则可以组成有效括号，有效括号长度+2。
    • 若为， 也不一定不是有效括号，还可能存在括号嵌套的情况，如”example2”, 这种情况则要判断 是否等于(，是则+2。该情况可以和上一种情况合并，都可表示为判断 是否成立。
  3. 当 是有效括号的结束字符时，要判断是否和之前的有效括号连续，如果连续要加上之前的长度。如”example3”， , 且 , 所以 。但是由于可以和之前的”()”连起来，所以 。

状态转移方程

时间复杂度&空间复杂度

  1. 时间复杂度:
  2. 空间复杂度:

LeetCode执行结果

  • 执行用时 : 4 ms, 在所有 C++ 提交中击败了 **95.63%**的用户。
  • 内存消耗 : 9.8 MB, 在所有 C++ 提交中击败了 **15.58%**的用户。

感受

其实动规比较简单，有套路可循。尤其是和字符串有关的题目，基本都与子串有关。但是难在子问题的划分，比如这道题中定义 表示以第i个字符结尾的字符串中最长的有效括号长度，这样就比较简单。而我之前想的是定义为子串中最长有效括号的长度，到后面很难处理。

代码

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
	int longestValidParentheses(string s)
	{
		if(s.empty())
		{
			return 0;
		}

		vector<int> dp(s.length(),0);
		dp[0] = 0;
		for(int i=1; i<s.length(); i++)
		{
			if(s[i] == ))
			{
				if(i - dp[i-1] -1 >= 0 &&  s[i - dp[i-1] -1] == ()
				{
					if(i - dp[i-1] -2 >=0)
					{
						dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] -2];					
					}
					else
					{
						dp[i] = 2 + dp[i-1];					
					}					
				}				
			}	
			else
			{
				dp[i] = 0;
			}
		}
		return *max_element(dp.begin(), dp.end());
	}
};

int main()
{
	string str;
	std::cout << "input:";
	std::cin >> str;
	Solution s;
	std::cout<<s.longestValidParentheses(str)<<std::endl;
	return 0;
}