首页 > 代码库 > [LeetCode]Longest Valid Parentheses, 解题报告
[LeetCode]Longest Valid Parentheses, 解题报告
题目
Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.、
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.、
思路
网上有牛人碰到这种问题第一反应就是DP,而我赶紧用栈处理这种括号匹配更简单一些,毕竟当初数据结构课上将栈匹配括号还是花了不少时间的。
这里直接用栈计算匹配括号的数量,然后 × 2得到长度是不对的,因为题目求的是连续最长括号匹配数,突出连续两个字。
因此,我们可以采用“标记”的方法,用栈维持左括号的下标,遇到一对匹配的括号,可以将其对应()在原先字符串的位置赋值一个特殊字符‘a‘,匹配结束后,计算连续a的长度即可。
AC代码
public class Solution { public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack<Integer>(); StringBuilder sBuilder = new StringBuilder(s); for (int i = 0; i < s.length(); i++) { if (sBuilder.charAt(i) == ‘(‘) { stack.push(i); } else { if (stack.isEmpty()) { continue; } else { sBuilder.setCharAt(i, ‘a‘); sBuilder.setCharAt(stack.pop(), ‘a‘); } } } int max = 0, len = 0; for (int i = 0; i < sBuilder.length(); i++) { if (sBuilder.charAt(i) == ‘a‘) { len++; max = Math.max(max, len); } else { len = 0; } } return max; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。