©2020-2024 ioDraw All rights reserved,
Privacy Policy
合法括号序列需要满足：
* 左右括号数量相同
* 任意一个前缀中，左括号数量≥右括号数量
题目：leetcode301.删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
思路
：首先根据合法序列要求求出需要删除的左括号数量和右括号数量。然后进行dfs删除多余的左右括号。为确保处理后的字符串满足左右括号数量相同，需要另一个参数cnt。当有连续的左右括号需要删除时，首先求出连续的左右括号数量，然后直接判断将连续的左右括号全部删完是否≤需要删除的左右括号数量，满足的话，直接删除，否则少删除一个左右括号，依次循环。
代码：
class Solution { List<String> res = new ArrayList<>(); public List<String>
removeInvalidParentheses(String s) { int n = s.length(); int l = 0,r = 0;
for(int i = 0;i < n;i++) { //统计需要删除的左右括号数量 char c = s.charAt(i); if(c == '(') {
l++; } else if(c == ')') { if(l == 0) { r++; } else { l--; } } }
dfs(s,0,"",0,l,r); // 第一个0是字符串索引，第二个0是path左右括号数量差值 return res; } public void
dfs(String s,int u,String path,int cnt,int l,int r) { if(u == s.length()) {
if(cnt == 0) { res.add(path); } return; } char c = s.charAt(u); if(c == '(') {
int k = u; while(k < s.length() && s.charAt(k) == '(') { // 统计连续的左括号数量 k++; } l
-= k - u; for(int i = k - u;i >= 0;i--) { // i是删除的左括号数量 if(l >= 0) {
dfs(s,k,path,cnt,l,r); } path += '('; l++; cnt++; } } else if(c == ')') { int k
= u; while(k < s.length() && s.charAt(k) == ')') { // 统计连续的右括号数量 k++; } r -= k
- u; for(int i = k - u;i >= 0;i--) { // i是删除的右括号数量 if(cnt >= 0 && r >= 0) {
dfs(s,k,path,cnt,l,r); } path += ')'; r++; cnt--; } } else {
dfs(s,u+1,path+s.charAt(u),cnt,l,r); } } }
题目：leetcode32. 最长括号序列
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
提示：
* 0 <= s.length <= 3 * 104
* s[i] 为 '(' 或 ')'
思路：（栈）首先需要一个分隔符start，分隔一个个区间，不同区间之间不可能结合在一起形成新的合法括号序列。
证明：每个区间满足任意前缀中左括号数量大于等于右括号数量，并且最后一个是‘)’，使得右括号数量比左括号数量多一。a区间s[i,j]，b区间s[j+1,k]，将其合并成c区间s[u,p]，其中s[u,j]是属于a区间的，该区间必然满足右括号数量大于左括号数量，所以直接不满足合法括号序列的要求。
从头到尾遍历字符串，当遇到‘(’时，将其序号压入栈中；当遇到‘)’时，判断栈中是否存在元素，如果存在元素，先将其弹出
，弹出后栈为空，那么此时的合法序列长度为i-start，否则合法序列长度为i-stk.peek()（此时stk.peek()是最近的一个未被匹配的左括号）。栈中不存在元素时，那么此时i作为一个新的分隔符，start=i。
class Solution { public int longestValidParentheses(String s) { Stack<Integer>
stk = new Stack<>(); int res = 0; for(int i = 0, start = -1;i < s.length();i++)
{ if(s.charAt(i) == '(') { stk.push(i); } else { if(stk.size() > 0) {
stk.pop(); if(stk.size() == 0) { res = Math.max(res,i-start); } else { res =
Math.max(res,i-stk.peek()); } } else { start = i; } } } return res; } }