LeetCode | 32. Longest Valid Parentheses

最新推荐文章于 2022-09-01 00:56:47 发布

1LOVESJohnny

最新推荐文章于 2022-09-01 00:56:47 发布

阅读量203

点赞数

分类专栏： LeetCode 文章标签： Leetcode

本文链接：https://blog.csdn.net/iLOVEJohnny/article/details/85484070

版权

LeetCode 专栏收录该内容

285 篇文章

订阅专栏

题目：

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
		vector<int> dp(s.length() + 1, 0);
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == ')' && i > 0)
			{
				if (s[i - 1] == '(')
				{
					dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
					maxLen = max(dp[i], maxLen);
				}
				else // s[i - 1] == ')'
				{
					if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
					{
						dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
						maxLen = max(dp[i], maxLen);
					}
				}
			}
		}
		return maxLen;
    }
};

感悟：

回顾2018，年初告别学校，一切拉开序幕。工作是一个新的阶段，发生了一些变化，我也重新开始思考很多东西。其中，有初期面对变化的勇敢，到后期面对变化的犹豫，心态随着时间和情况，发生了微妙的转变。不过，慎重的决定，我相信，不管如何，我都会鼓起勇气去面对。加油吧！希望新的一年，我可以少喊一些口号，真的做一些事情。近期家中的变故也给我很大的冲击，愿一切都好，还是要满怀希望的看待一切。加油！

最后，新年快乐！