**# 题目分类

Leetcode 一共九道括号题

20 Valid Parentheses
32 Longest Valid Parentheses
22 Generate Parentheses
( Laicod 66 All valid permutation of parentheses)
(Laicode 179 All valid permutation of parenthese II)
241 Different Ways to Add Parentheses
301 Remove Invalid Parentheses (FB排名第一的高频）
678 Valid Parenthesis String
856 Score of Parentheses
921 Minimum Add to Make Parentheses Valid
1021 Remove Outermost Parentheses

这九题可以分为几种类型。

1。验证括号是否Valid （20， 678）
2。找最长Valid（32）
3。生成Valid的括号 （22）
4。把不valid的修改成valid的
a. 减 (301）
b. 加 (921)
5。其他 （241, 856, 1021，这次不讨论了，跟括号关系不大）

括号的基本性质

1.左右括号数量要相等 (), ()(), (()), (()()), )(, ())(()
2. 每一个左括号要在右边找到它的mate，每一个右括号要在左边找到跟它的mate。 我们把和一个括号对应的括号叫做它的mate。
3. 每一对括号里面的括号串也要满足同样的性质。（相当于一个recursion)

基本方法

1。 Stack ， 万能， 但是要额外的空间
2。 数数量： 在判断valid时非常有用。（只对一种括号有效)
从左往右扫， 左+1， 右-1，负数就肯定不valid （不要太在意这句描述，To be detailed later)
3。DFS search： 在产生括号，修改括号时非常有用。

例题

1. 判断是否valid

20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. Valid Parentheses

栈的做法

先说只有一种括号的 ()。

从左向右扫：
1.左括号push进栈。
2.右括号则pop操作。如果栈为空则非法
扫到末尾如果栈不是空的也是非法

Deque<Character> deque = new ArrayDeque<>();
for (char c : str.toCharArray()) {
  if (c == '(') deque.push(c);
  else if (!deque.isEmpty()) deque.pop();
  else return false;
}
return deque.isEmpty();

如果有多种括号：

遇到左括号无脑push进栈，遇到右括号从栈顶pop，如果pop出来这个值不是当前括号的mate，则invalid. 只是多了一个检查是否是mate的操作.

Deque<Charcter> deque = new ArrayDeque<>();
for (char c : str.toCharArray()) {
  if ("({[".indexOf(c) >= 0) deque.push(c);
  else if (!deque.isEmpty() && isMate(deque.pop(), c)) continue;
  else return false;
}
return deque.isEmpty();

再说数括号数目的做法

先说只有一种括号的

基本出发点还是从栈。栈里面是不是存的都是左括号？
既然都是左括号，我干嘛要存，我只要记有多少个就可以了。

int left = 0;
for (char c : str.toCharArray()) {
  if (c == '(') left++; //相当于栈的push操作
  else if (left > 0) left--; //相当于栈的pop操作
  else return false; //栈为空了
}
return left != 0; //检查栈是不是为空

再说有多种括号的

这时这个方法好像就不能做了。因为括号种类不一样，所以不能只记数量， 也不能只记三种括号的数量，必须要记三种括号的先后关系。所以还得用栈。

但是请不要因此对数数目的方法失去信心，它依然是一种很强大的武器。

678 Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

栈的做法

遇到 * 怎么弄？
暴力解可以分成两个分支，一个分支把它当左括号，一个分支把它当右括号。看哪个分支valid。时间复杂度太高
也可以直接丢到栈里面去，可是从栈里pop出来的时候又遇到了相同的难题。

正确做法是开两个栈（May 5 更新）
左括号一个栈，星号一个栈，push进去的是它的坐标。

public boolean checkValidString(String s) {
        Deque<Integer>  lDeque = new ArrayDeque<>(), starDeque = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') lDeque.push(i);
            else if (c == '*') starDeque.push(i);
            else {
                if (!lDeque.isEmpty()) lDeque.pop();
                else if (!starDeque.isEmpty()) starDeque.pop();
                else return false;
            }
        }
        while (!lDeque.isEmpty()) { //这时还有一些没有配对的左括号和星号
            if (starDeque.isEmpty() || lDeque.peek() > starDeque.peek()) return false;
            lDeque.pop();
            starDeque.pop();
        }
        return true;
    }

数括号数目的做法

从左往右数，左括号加一，右括号减1， *号 单独记

int left = 0, star = 0;
for (char c : str.toCharArray()) {
  if (c == '(') left++;
  else if (c == '*') star++;
  else if (left > 0) left--;
  else if (star > 0) start--;
  else return false;
}
return left == 0; (这样不对）反例 ( *

return left <= star; (这样也不对）反例  * (

问题在于我们只是帮每一个右括号找到了mate。对于左括号，由于 ( 和 *出现的顺序不清楚，不一定能match上。由于我们只记数量，丢掉了顺序信息所以并不能给出正确答案。
解决办法， 再从右向左扫一遍，确保每个右括号找到自己的mate
上面的程序还得再加一段

star = 0;
int right = 0;
for (int i = str.length() - 1; i >= 0; i--) {
  char c = str.charAt(i);
  if (c == ')') right++;
  else if (c == '*') star++;
  else if (right > 0) right--;
  else if (star > 0) star--;
  else return false;
}
return true;

时间复杂度O(N), 空间复杂度O(1)
这个做法不难操作，便于记忆，但难点在于怎么证明它是对的？
如果有人问你，你第一遍时把星号做为左括号，第二遍时把星号做为右括号，你怎么能保证你没把同一个星号既做为左括号又作为右括号？

• ) | ( ( ) *
  （）|（）|（（ * *
  （））|（）|（）|
  前两个数完之后left = 0, star = 0, 这时前两个自成一体。你可以每遇到一个（left = 0 && star == 0)时就把前面的扔掉。 相当于这个地方有个天然的分隔。这样可以把一个字符串分为不同的segments.
  除了最后一个segment之外，所有之前的segment都是自成一体的，自我平衡，不依赖于外界。
  如果最后一个segment也是自成一体的，根本不需要从右往左再扫一遍。然而最后一个segment可能还有left != 0。 这个例子 ) | ( ( ) * 里扔掉第一个segment之后只剩 (( )*这个segment。这时你会发现这里面所有的右括号match的都是左括号，星号根本没和右括号match(因为左括号还没用完啊）。
  l = 2, * = 1

官方答案的做法 ( Greedy解法)

   public boolean checkValidString(String s) {
      int lo = 0, hi = 0;
      for (char c: s.toCharArray()) {
          lo += c == '(' ? 1 : -1;
          hi += c != ')' ? 1 : -1;
          if (hi < 0) break;
          lo = Math.max(lo, 0);
      }
      return lo == 0;
   }

2. 找最长Valid（32）

32 Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

数数量的方法

从左到右数，两个变量l, r， 遇到左 l加一，遇到右 r加一。

int l = 0, r = 0;
for (char c : str.toCharArray()) {
  if (c == '(') l++;
  else r++;
  if (r == l) {
    ans = Math.max(ans, l + r); //左右相等，可以更新结果
  } else if (r > l) { //这个点肯定绕不过去了。要清零 “（ ））（ ）”
    l = 0;
    r = 0;
  }
}
return ans; (这句话也是不对的，反例 ((()

同样也得再从右再往左走一遍，需要加上下面这一段

r = 0,
for (int i = str.length() - 1; i >= 0; i--) {
  char c = str.charAt(i);
  if (c == ')') r++;
  else l++;
  if (r == l) {
    ans = Math.max(ans, l + r);
    } else if (l > r) {
    l = 0;
    r = 0;
    }
  }
return ans;

DP做法

dp[i], OFFSET by 1 的 int array
State definition:
以第i - 1个字母为结尾的最长valid括号字符串
Induction rule:
dp[i] = { 0 if str.charAt(i - 1) == '(';
{ 2 + dp[i - 2] if str.charAt(i - 2) == '(' && str.charAt(i - 1) == ')';
{ 2 + dp[i - 1] if (s.charAt(i - 1 - dp[i - 1]) == '(' && str.charAt(i - 1) == ')';
{ 0 if (s.charAt(i - 1 - dp[i - 1]) != '(' && str.charAt(i - 1) == ')';
初始化:
dp[0] = 0; dp[1] = 0;
ans:
Math.max(dp[i]) for i = 0 to N;

public int longestValidParentheses(String s) {
       int maxans = 0;
       int dp[] = new int[s.length()];
       for (int i = 1; i < s.length(); i++) {
           if (s.charAt(i) == ')') {
               if (s.charAt(i - 1) == '(') {
                   dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
               } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                   dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
               }
               maxans = Math.max(maxans, dp[i]);
           }
       }
       return maxans;
   }

3. 生成Valid的括号

22 Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

这就没啥好说的，直接DFS了

每一轮分成两叉，左括号和右括号，然后要判断一下这一叉是否是合法的。

public List<String> generateParenthesis(int n) {
       List<String> ans = new ArrayList<>();
       dfsHelper(0, 0, n, "", ans);
       return ans;
   }

   private void dfsHelper(int l, int r, int n, String str, List<String> ans) {
       if (l == n && r == n) {
           ans.add(str);
           return;
       }
       if (l < n) dfsHelper(l + 1, r, n, str + '(', ans);
       if (r < l) dfsHelper(l, r + 1, n, str + ')', ans);
   }

Laicode 179 All valid permutation of parenthese II

Get all valid permutations of l pairs of (), m pairs of <> and n pairs of {}.

这时就不能光数数量了，需要一个栈， 每次放右括号的时候要检查一下能不能和栈顶的元素匹配上。

4. 把不valid的修改成valid的

921 Minimum Add to Make Parentheses Valid

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

   public int minAddToMakeValid(String S) {
       int l = 0, r = 0;
       for (char c : S.toCharArray()){
           if (c == '(') l++;
           else if (l > 0) l--;
           else r ++;
       }
       return l + r;
   }

为什么这里不需要左右各跑一遍？

301 Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

先讨论变种 返回任意一种valid的解。

FB高频题只要求给作任意一种valid的解就可以了。

思路： 先数一下看多了几个括号
( ) ( ) ) ( ) ( ( ) 从左往右数发现第五个括号多了
( ) ( ) ) ( ) ( ( ) 从右往左数发现右边数第三个括号多了
如果说只要求返回一个valid的解，直接把这两个括号删掉返回就可以。

int N = str.length();
boolean[] marker = new boolean[N];
int l = 0;
for (int i = 0; i < N; i++) {
  char c = str.charAt(i);
  if (c == '(') l++;
  else if (c == ')' && l > 0) l--;
  else marker[i] = true;
}
int r = 0;
for (int i = N - 1; i >= 0; i--) {
  char c = str.charAt(i);
  if (c == ')') r++;
  else if (c == '(' && r > 0) r--;
  else marker[i] = true;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
  if (!marker[i]) sb.append(str.charAt(i));
}
return sb.toString();

返回所有可行解

先找出到底最少要删掉多少括号。然后DFS删就好了。但是要注意去重

主逻辑

   public List<String> removeInvalidParentheses(String s) {
       // 先找出到底最少要删掉多少括号
       int[] redundant = getRedundant(s);
       //然后DFS删就好了
       List<String> ans = new ArrayList<>();
       dfs(redundant[0], redundant[1], s, ans, "", 0);
       return ans;
   }

DFS 逻辑

private void dfs(int lm, int rm, String s, List<String> ans, String cur, int index) {
       if (lm + rm == 0) {
           if (isValid(cur + s.substring(index) )) {
               ans.add(cur + s.substring(index));
           }
           return;
       }
       for (int i = index; i < s.length(); i++) {
            if (i != index && s.charAt(i) == s.charAt(i - 1)) continue; //去重
           if (s.charAt(i) == '(' && lm > 0) {
               dfs(lm - 1, rm, s, ans, cur + s.substring(index, i), i + 1);
           }
           if (s.charAt(i) == ')' && rm > 0) {
               dfs(lm, rm - 1, s, ans, cur + s.substring(index, i), i + 1);\
           }
       }
   }

还有两个helper函数

private int[] getRedundant(String s) {
       int l = 0, r = 0;
       for (char c : s.toCharArray()) {
           if (c == '(') l++;
           else if (c == ')' && l > 0) l--;
           else r++;
       }
       return new int[]{l, r}; //这里不需要左右各跑一遍
 }

private boolean isValid(String s) {
       int[] lr = getRedundant(s);
       return lr[0] + lr[1] == 0;
}

另外一种做法
**https://leetcode.com/problems/remove-invalid-parentheses/discuss/75034/Easiest-9ms-Java-Solution

public List<String> removeInvalidParentheses(String s) {
    int rmL = 0, rmR = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            rmL++;
        } else if (s.charAt(i) == ')') {
            if (rmL != 0) {
                rmL--;
            } else {
                rmR++;
            }
        }
    }
    Set<String> res = new HashSet<>();
    dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
    return new ArrayList<String>(res);
}

public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {
    if (rmL < 0 || rmR < 0 || open < 0) {
        return;
    }
    if (i == s.length()) {
        if (rmL == 0 && rmR == 0 && open == 0) {
            res.add(sb.toString());
        }        
        return;
    }

    char c = s.charAt(i); 
    int len = sb.length();

    if (c == '(') {
        dfs(s, i + 1, res, sb, rmL - 1, rmR, open);         // not use (
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (

    } else if (c == ')') {
        dfs(s, i + 1, res, sb, rmL, rmR - 1, open);             // not use  )
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);       // use )

    } else {
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);   
    }

    sb.setLength(len);        
}