leetcode 32 Longest Valid Parentheses

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 “()()”

题目地址:leetcode Longest Valid Parentheses

题目大意:给你一个括号组成的字符串,要求求出最长的合法括号长度

 

一开始想,每次计算的时候用当前右括号,合法长度的开头,但是有

)(((((()())()()))()(()))( 应该为22. 而我合法长度的开头从1开始,因为后面没有匹配第一个和第二个左括号的,所以wa了。

后来开了个数组Match,用来标记当前左括号和哪个右括号匹配。

之后进行一次扫描,过程主要如下:

  • 用temp标记合法连续的上一块总长度
  • 若match[i]!=0, 每次i移动的位置直接移动到右括号的位置(即match[i]),因为这一段必定是合法的。
  • 更新ans

 

 

之后搜了别人怎么做的。

有的直接用个bool数组标记括号是否匹配,如果匹配为1,之后进行统计即可。 更简单一些。

参考代码如下:

c++:

python

 

还可以用栈记录上一个括号的位置和之前连续的长度。

若能和上一段拼接起来,就合并。合并比(())()这种情况,最后一个)的时候,发现可以和之前的合并。

 

 

下面是最简洁的写法了,

  • 遇到(就把下标放入,
  • 遇到)就先pop一个,
    • 如果栈为空,说明没匹配,把当前下标push进去,作为新的一段的开始
    • 栈不为空,说明合法,长度为i – 栈顶的下标

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 32 Longest Valid Parentheses
本文地址:https://www.hrwhisper.me/leetcode-longest-valid-parentheses/

您的支持将鼓励我继续创作!

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *