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.
[balabala] 自己只想出来DP包装的枚举实现,妥妥地超时。网上搜到了巧妙的解答,好好吸其精华。
public class Solution { // method 4: O(n) // dp[i]: 包含s.charAt[i - 1]的最长有效括号串长度 // 所有'('对应的dp[i] == 0 // 位置i - 1处为')' 时,若前面有匹配的'(', 其位置记为leftPos, // dp[i]=当下(...)长度 + leftPos前一个位置处的最长有效括号串长 public int longestValidParentheses(String s) { if (s == null || s.length() < 2) return 0; int N = s.length(); int[] dp = new int[N + 1]; LinkedList<Integer> stack = new LinkedList<Integer>(); int max = 0; for (int i = 1; i <= N; i++) { char c = s.charAt(i - 1); if (c == '(') { stack.push(i); } else if (!stack.isEmpty()){ int leftPos = stack.pop(); dp[i] = i - leftPos + 1 + dp[leftPos - 1]; max = Math.max(max, dp[i]); } } return max; } // method 3: O(n) // dp[i]表示从索引i到结尾的字符串的前缀的最长有效括号对长度 // http://www.cnblogs.com/huntfor/p/3886111.html // 计算方向:自右向左 public int longestValidParentheses3(String s) { if (s == null || s.length() == 0) { return 0; } int n = s.length(); int[] dp = new int[n]; dp[n - 1] = 0; int max = 0; for (int i = n - 2; i >= 0; i--) { if (s.charAt(i) == '(') { int j = i + 1 + dp[i + 1]; //寻找最长有效前缀的后驱 if (j < n && s.charAt(j) == ')') { dp[i] = dp[i + 1] + 2; if (j + 1 < n) dp[i] += dp[j + 1]; } max = Math.max(max, dp[i]); } } return max; } // method 2: O(n) // http://www.cnblogs.com/lichen782/p/leetcode_Longest_Valid_Parentheses.html // http://blog.csdn.net/worldwindjp/article/details/39460161 // 实现中的last变量记录的是有效串开始位置的前面一个下标, // 也是最后一个无法匹配的')'的下标,每个无法匹配的')'是一组组有效串的分界点 public int longestValidParentheses(String s) { if (s == null || s.length() == 0) { return 0; } int max = 0; int last = -1; LinkedList<Integer> stack = new LinkedList<Integer>();// 栈中元素是每个入栈'(' 的下标 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { if (stack.isEmpty()) { last = i; // 遇到')'且无人匹配,更新last为当前下标 } else { stack.pop(); if (!stack.isEmpty()) { max = Math.max(max, i - stack.peek()); } else { max = Math.max(max, i - last); } } } } return max; } // method 1 : 枚举,O(n^3), 超时 // dp[i][j] : tells whether s.substring(i, j) is a valid parentheses string public int longestValidParentheses1(String s) { if (s == null || s.length() == 0) { return 0; } // 预处理 - 不顶用, 通过分析算法的时间复杂度可知是杯水车薪。 StringBuilder sb = new StringBuilder(s); int beg = 0; int end = s.length() - 1; for (int i = beg; i <= end; i++) { if (s.charAt(i) == ')') beg++; else break; } for (int i = end; i >= beg; i--) { if (s.charAt(i) == '(') end--; else break; } s = s.substring(beg, end + 1); int n = s.length(); boolean[][] dp = new boolean[n][n]; // 长度为奇数的子串不可能平衡, 无需计算 // for (int i = 0; i < n; i++) { // for (int j = i; j < n; j += 2) { // dp[i][j] = false; // } // } // 判断所有长度为2的子串 for (int i = 0; i < n - 1; i++) { dp[i][i + 1] = s.charAt(i) == '(' && s.charAt(i + 1) == ')'; } // 从小到大依次判断其他长度的子串, O(n^3) for (int len = 4; len <= n; len += 2) { // O(n) for (int i = 0; i < n - len + 1; i++) { // O(n) int j = i + len - 1; dp[i][j] = s.charAt(i) == '(' && s.charAt(j) == ')' && dp[i + 1][j - 1]; for (int k = i + 1; k < j - 1; k += 2) { // O(n) dp[i][j] |= dp[i][k] && dp[k + 1][j]; } } } // 逆推,找到最长平衡串 for (int len = n; len >= 2; len -= 2) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (dp[i][j]) return len; } } return 0; } }
相关推荐
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
加油站 leetcode 力码锈 问题 # 标题 命令 1 cargo run ...3-longest-substring-without-repeating-...20-valid-parentheses 21 cargo run --bin 21-merge-two-sorted-lists 27 cargo run --bin 27-remove-element 28
Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock...
java lru leetcode ...Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./leetcode/动态规划-Maximum Length of Repeated Subar
java lru leetcode :ice_cream: LeetCode ...Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
Longest Common Prefix:这道题和大家思路一样,都是取第一个字符串里的字节与后面的进行比较,只是要注意,针对空vector的返回,针对vector只有一个值时候的返回,和一些通过设置更好初始值进行优化。 20. Valid ...
Longest Common Prefix 运行时间:40 毫秒内存使用:13.9 MB 20. Valid Parentheses 运行时间:40 毫秒内存使用:13.8 MB 22. Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Leetcode 32 Longest Valid Parentheses (最长有效括号) 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2...
Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to ...
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写并配有输入输出样例 代码清单如下: 序号 题目 程序源码 ...Parentheses.cpp 22 括号生成 G
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** ...Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
leetcode怎么改密码 Code leetcode easy 测试一下本地的... emmmmm之前修改了一下,现在用ssh提交 应该不用输入密码了吧 ~~emmmmm 先在这里立个flag!!...Longest Valid Parentheses :cross_mark:暴力解法(未通过)
第四章 Leetcode 题解 ...20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
LeetCode去除数组重复元素 说明 在leetcode上的题目 ...Parentheses(有效的括号) 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足:左括号必须用相同类型的
lru cache leetcode #算法解题报告 主要记录我每天做的题目,包括leetcode, 剑指offer等在线编程平台,以前做过的等时间够再一起分享。 使用swift解题 30-Day ...Parentheses 21.Merge Two Sorted L
Longest Valid Parentheses Largest Rectangle in Histogram Evaluate Reverse Polish Notation Implement Stack using Queues 队列 Implement Queue using Stacks 二叉树 二叉树的遍历 Binary Tree Preorder ...