The legal bracket sequence needs to meet ：
* The number of left and right brackets is the same
* In any prefix , Number of left parentheses ≥ Number of right parentheses
subject ：leetcode301. Remove invalid parentheses
Give you a string of parentheses and letters s , Remove the minimum number of invalid parentheses , Make the input string valid .
Return all possible results . You can press Arbitrary order return .
thinking
： First, calculate the number of left parentheses and right parentheses to be deleted according to the legal sequence requirements . Then proceed dfs Remove extra left and right parentheses . To ensure that the processed string meets the same number of left and right parentheses , Another parameter is required cnt. When there are consecutive left and right parentheses that need to be deleted , First, find the number of consecutive left and right parentheses , Then directly judge whether to delete all the continuous left and right parentheses ≤ Number of left and right parentheses to be deleted , If satisfied , Delete directly , Otherwise, delete one less left and right parentheses , Cycle in sequence .
code ：
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++) { // Count the number of left and right parentheses to be deleted char c = s.charAt(i); if(c == '(') {
l++; } else if(c == ')') { if(l == 0) { r++; } else { l--; } } }
dfs(s,0,"",0,l,r); // first 0 Is a string index , the second 0 yes path Difference between the number of left and right parentheses 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) == '(') { // Count the number of consecutive left parentheses k++; } l
-= k - u; for(int i = k - u;i >= 0;i--) { // i Is the number of left parentheses deleted 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) == ')') { // Count the number of consecutive right parentheses k++; } r -= k
- u; for(int i = k - u;i >= 0;i--) { // i Is the number of right parentheses deleted 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); } } }
subject ：leetcode32. Longest bracket sequence
Give you one that only contains '(' and ')' String of , Find the longest effective （ Correct and continuous format ） Length of bracket substring .
Tips ：
* 0 <= s.length <= 3 * 104
* s[i] by '(' or ')'
thinking ：（ Stack ） You need a separator first start, Separate sections , Different intervals cannot be combined to form a new sequence of legal brackets .
prove ： Each interval satisfies that the number of left parentheses in any prefix is greater than or equal to the number of right parentheses , And the last one is ‘)’, Make the number of right parentheses more than the number of left parentheses .a section s[i,j],b section s[j+1,k], Merge them into c section s[u,p], among s[u,j] Belongs to a Interval , This interval must meet the requirement that the number of right parentheses is greater than the number of left parentheses , Therefore, it directly does not meet the requirements of legal bracket sequence .
Traverse the string from beginning to end , When encountered ‘(’ Hour , Press its serial number into the stack ; When encountered ‘)’ Hour , Determine whether there are elements in the stack , If an element exists , Pop it up first
, Stack is empty after pop-up , Then the legal sequence length at this time is i-start, Otherwise, the legal sequence length is i-stk.peek()（ here stk.peek() Is the latest unmatched left parenthesis ）. When there is no element in the stack , So at this time i As a new separator ,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; } }
Technology