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 "()()"

思路与解法

看到这道题目首先想到的就是经典的括号匹配问题（利用栈），这道题与之有所不同，整个字符串并不一定满足括号匹配，我们所要找的是最长的括号匹配的子串。 第一种方法就是进行N次括号匹配：输入字符串的长度为N，则以0~N-1位置的字符为起点向后进行一次括号匹配，获得匹配的长度；最终返回所有长度中的最大值即可。时间复杂度为O($N^2$)。（这种方法我并没有使用，并不知道能否通过测试。） 下面介绍一种效率更高的算法： 定义数据dp[i]表示位于栈中第i个位置(从下到上)的连续出栈的字符串长度。（使用dp表示，是因为最初打算使用动态规划的思想来做，但最终实现与动态规划关系并不大） 同样利用栈的思想，从左到右遍历整个字符串S：1、如果S[i]=='('，则将(压入栈中；2、否则的话：①如果当前栈顶元素为(，即stack[stackLen-1]=='('，然后存在了一对匹配的括号，更新dp数组：dp[stackLen-1] = dp[stackLen-1] + dp[stackLen] + 2，dp[i]由三部分组成，之前在该位置弹出的字符串数量dp[i]、在下一个位置上弹出的字符串数量dp[i+1]、以及新增的一堆括号；然后将dp[i+1]置为0。②否则的话，将当前元素压入到栈中。 下面以一个具体实例来介绍一下该算法：(()))(((()))()) 上述图示也间接说明了dp[i+1]对dp[i]所起的作用

代码实现

此算法我才用go语言实现

func longestValidParentheses(s string) int { stack := make([]byte, 0) dp := make([]int, len(s)+1) max := 0 if s=="" { return 0 } stack = append(stack, s[0]) for i:=1; i<len(s); i++ { if s[i] == '(' { stack = append(stack, s[i]) } else { stackLen := len(stack) if stackLen > 0 && stack[stackLen-1] == '(' { stack = stack[:stackLen-1] dp[stackLen-1] = dp[stackLen-1] + dp[stackLen] + 2 dp[stackLen] = 0 } else { stack = append(stack, s[i]) } } } for i:=0; i<len(s)+1; i++ { if max < dp[i] { max = dp[i] } } return max }

测试结果

此算法的时间复杂度为$O(N)$，效率较高：