合法括号序列的充要条件

  1. 任意前缀中左括号的数量大于等于右括号的数量
  2. 左右括号的个数相等

性质：

  1. 如果要求最长有效括号的个数，要记住每个最长有效括号串是各不相交的。

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：
输入：s = “”
输出：0


提示：

  • 0 <= s.length <= 3 * 104

  • s[i] 为 '(' 或 ')'

    1. //方法一：栈
    2. class Solution {
    3.   public int longestValidParentheses(String s) {
    4.       Deque<Integer> q = new LinkedList<>();
    6.       //方便处理边界往栈内加个-1
    7.       q.push(-1);
    9.       int ans = 0;
    10.       for (int i = 0; i < s.length(); i++) {
    11.           char ch = s.charAt(i);
    12.           if (ch == '(')
    13.               q.push(i);
    14.           else {
    15.               q.pop();
    16.               if (q.isEmpty())
    17.                   q.push(i);
    18.               else
    19.                   ans = Math.max(ans, i - q.peek());
    20.           }
    21.       }
    22.       return ans;
    23.   }
    24. }
    1. 方法二：贪心，左右各遍历一轮
    2. class Solution {
    3.   public int longestValidParentheses(String s) {
    4.       int c1 = 0, c2 = 0, ans = 0;
    5.       for (int i = 0; i < s.length(); i++) {
    6.           char ch = s.charAt(i);
    7.           if (ch == '(')
    8.               c1++;
    9.           else {
    10.               c2++;
    11.               if (c2 == c1)
    12.                   ans = Math.max(ans, 2 * c2);
    13.               else if (c2 > c1)
    14.                   c2 = c1 = 0;
    15.           }
    16.       }
    17.       c1 = c2 = 0;
    18.       for (int i = s.length() - 1; i >= 0; i--) {
    19.           char ch = s.charAt(i);
    20.           if (ch == ')')
    21.               c1++;
    22.           else {
    23.               c2++;
    24.               if (c2 == c1)
    25.                   ans = Math.max(ans, 2 * c2);
    26.               else if (c2 > c1)
    27.                   c2 = c1 = 0;
    28.           }
    29.       }
    31.       return ans;
    32.   }
    33. }

    如果只从左往右遍历，"()(()()" 这种情况不能被正确处理，因为为无论什么时候 c1 >= c2 都成立，但是ans只能变为2，而不是4，因为中间多了一个 ( ，相反，从右往左遍历一次就能很好处理这种情况！ 类似的 "(()))()" 从右往左不能正确处理但是从左往右就可以

Acwing 4198. 最长合法括号子串

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         String s = sc.next();
  8.         int n = s.length();
  9.         int[] stk = new int[n + 1];
  10.         stk[0] = -1;
  11.         int p = 0;
  12.         int max = 0, cnt = 0;
  14.         for (int i = 0; i < n; i++) {
  15.             char c = s.charAt(i);
  16.             if (c == '(') {
  17.                 stk[++p] = i;
  18.             } else {
  19.                 int l = stk[p--];
  20.                 if (p < 0 || s.charAt(l) == ')'){
  21.                     stk[++p] = l;
  22.                     stk[++p] = i;
  23.                 } else {
  24.                     int len = i - stk[p];
  25.                     if (max < len) {
  26.                         max = len;
  27.                         cnt = 1;
  28.                     } else if (max == len) {
  29.                         cnt++;
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         if (max != 0)
  35.             System.out.println(max + " " + cnt);
  36.         else
  37.             System.out.println(0 + " " + 1);
  38.     }
  39. }

921. 使括号有效的最少添加

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

  • 它是一个空字符串，或者
  • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
  • 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：
输入：“())”
输出：1

示例 2：
输入：“(((“
输出：3

示例 3：
输入：“()”
输出：0

示例 4：
输入：“()))((“
输出：4

提示：

  1. S.length <= 1000
  2. S 只包含 '(' 和 ')' 字符。

思路：贪心，能选就选
题目转换，添加最少字符使整个字符串合法等价于删除最少字符使字符串合理

  1. //遍历一遍，找出多余的左括号和右括号的数量就是应该删除的最小字符个数
  2. class Solution {
  3.     public int minAddToMakeValid(String s) {
  4.         int c1 = 0, c2 = 0;
  5.         for (int i = 0; i < s.length(); i++) {
  6.             if (s.charAt(i) == '(')
  7.                 c1++;
  8.             else {
  9.                 if (c1 > 0)
  10.                     c1--;
  11.                 else
  12.                     c2++;
  13.             }
  14.         }
  15.         return c1 + c2;
  16.     }
  17. }

本题与32不同的是32题是找最长合法子串的长度，而本题相当于找最长合法子序列的长度，注意区别！！

Acwing 4207. 最长合法括号子序列

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：
输入：s = “()())()”
输出：[“(())()”,”()()()”]

示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,”(a)()()”]

示例 3：
输入：s = “)(“
输出：[“”]


提示：

  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • s 中至多含 20 个括号

思路：
921的进阶，不仅要找出最长合法子序列的长度，还要输出所有合法的最长子序列！
用 dfs + 剪枝
dfs时要注意保证当前保存的子串是合法的，即左括号数要大于右括号数
剪枝策略，对于一串连续的左括号或者右括号进行集中处理而不是一个一个的选择删或不删！

  1. class Solution {
  2.     List<String> res = new ArrayList<>();
  3.     StringBuilder sb = new StringBuilder();
  4.     public List<String> removeInvalidParentheses(String s) {
  5.         int n = s.length(), c1 = 0, c2 = 0;
  6.         for (int i = 0; i < n; i++) {
  7.             char ch = s.charAt(i);
  8.             if (ch == '(')
  9.                 c1++;
  10.             else if (ch == ')')
  11.                 if (c1 > 0)
  12.                     c1--;
  13.                 else
  14.                     c2++;
  15.         }
  16.         dfs(0, s, 0, c1, c2);
  17.         return res;
  18.     }
  20.     void dfs(int u, String s, int cnt, int c1, int c2) {
  21.         if (u == s.length()) {
  22.             if (cnt == 0)
  23.                 res.add(sb.toString());
  24.             return;
  25.         }
  27.         char ch = s.charAt(u);
  28.         if (ch != '(' && ch != ')') {
  29.             sb.append(ch);
  30.             dfs(u + 1, s, cnt, c1, c2);
  31.             sb.deleteCharAt(sb.length() - 1);
  32.         } else if (ch == '(') {
  33.             int k = u; 
  34.             while (k < s.length() && s.charAt(k) == '(')
  35.                 k++;
  36.             int len = k - u;
  37.             c1 -= len;
  38.             for (int i = len; i >= 0; i--) {
  39.                 if (c1 >= 0) {
  40.                     dfs(k, s, cnt, c1, c2);
  41.                 }
  42.                 sb.append('(');
  43.                 cnt++;
  44.                 c1++;
  45.             }
  46.             for (int i = len; i >= 0; i--) {
  47.                 sb.deleteCharAt(sb.length() - 1);
  48.             }
  49.         } else {
  50.             int k = u;
  51.             while (k < s.length() && s.charAt(k) == ')')
  52.                 k++;
  53.             int len = k - u;
  54.             c2 -= len;
  55.             for (int i = len; i >= 0; i--) {
  56.                 if (cnt >= 0 && c2 >= 0)
  57.                     dfs(k, s, cnt, c1, c2);
  58.                 sb.append(')');
  59.                 cnt--;
  60.                 c2++;
  61.             }
  62.             for (int i = len; i >= 0; i--) {
  63.                 sb.deleteCharAt(sb.length() - 1);
  64.             }
  65.         }
  66.     }
  67. }

678. 有效的括号字符串

给定一个只包含三种字符的字符串：（，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  5. 一个空字符串也被视为有效字符串。

示例 1:
输入: “()”
输出: True

示例 2:
输入: “()”
*输出: True

示例 3:
输入: “())”
*输出: True

注意:

  1. 字符串大小将在 [1，100] 范围内。

思路：
方法一：使用两个栈，一个存储*，另一个存储(
方法二：从左往右遍历一遍再从右往左遍历一遍，因为如果是合法字符串，无非三种情况

  1. 左右括号匹配，*号数量无所谓，从右往左和从左往右都能执行
  2. 左括号数量多于右括号，但*号可以填充部分右括号使其有效

  3. 右括号数量多于左括号，但*号可以填充部分左括号使其有效

    无效是不是一定能返回false？
    答：是的，从左到右是将全部看作左括号，能成功遍历的条件是每个右括号都有一个左括号或者与之对应
    从右到左是将全部看作右括号，能成功遍历的条件是每个左括号都有一个右括号或者与之对应

    1. //方法一：
    2. class Solution {
    3.  public boolean checkValidString(String s) {
    4.      Deque<Integer> stack = new LinkedList<>();
    5.      Deque<Integer> star = new LinkedList<>();
    7.      for (int i = 0; i < s.length(); i++) {
    8.          char ch = s.charAt(i);
    9.          if (ch == '(')
    10.              stack.offer(i);
    11.          else if (ch == '*') 
    12.              star.offer(i);
    13.          else {
    14.              if (!stack.isEmpty())
    15.                  stack.pollLast();
    16.              else if(!star.isEmpty())
    17.                  star.pollLast();
    18.              else
    19.                  return false;
    20.          }
    21.      }
    22.      if (stack.isEmpty())
    23.          return true;
    24.      else {
    25.          while (!stack.isEmpty()) {
    26.              if (star.isEmpty() || star.peekLast() < stack.peekLast())
    27.                  return false;
    28.              stack.pollLast();
    29.              star.pollLast();
    30.          }
    31.          return true;
    32.      }
    33.  }
    34. }
    1. //方法二：左右各遍历一遍
    2. class Solution {
    3.  public boolean checkValidString(String s) {
    4.      int l = 0, r = 0, star = 0;
    5.      for (int i = 0; i < s.length(); i++) {
    6.          char ch = s.charAt(i);
    7.          if (ch == '(')
    8.              l++;
    9.          else if (ch == '*')
    10.              star++;
    11.          else {
    12.              if (l > 0)
    13.                  l--;
    14.              else if (star > 0)
    15.                  star--;
    16.              else
    17.                  return false;
    18.          }
    19.      }
    21.      l = r = star = 0;
    22.      for (int i = s.length() - 1; i >= 0; i--) {
    23.          char ch = s.charAt(i);
    24.          if (ch == ')')
    25.              r++;
    26.          else if (ch == '*')
    27.              star++;
    28.          else {
    29.              if (r > 0)
    30.                  r--;
    31.              else if (star > 0)
    32.                  star--;
    33.              else
    34.                  return false;
    35.          }
    36.      }
    37.      return true;
    38.  }
    39. }

    5948. 判断一个括号字符串是否有效

    思路：678题换了种问法！

AcWing 1070. 括号配对

括号配对输出具体方案

Acwing 2004. 错字

问题描述：
一个括号串可能存在某位字符发生变化，即)变为(，或者是)变为(
请找到所有可能出错的位置，输出总个数

思路：
如果符号串本身合法，输出0即可
否则说明存在某位发生变化，先找出是做左括号多还是右括号多，然后遍历字符串找到所有能修改的位置
以左括号多为例：
说明需要将某个左括号改为右括号
倒着遍历，用一个计数器cc记录右括号 - 左括号的数量，若当前位置为(且cc >= 0说明该左括号可以变为右括号，若当前位置cc < 0说明后面位置的左括号即使变为右括号也不能合法配对
如果是右括号更多，对称求解即可