算法思维(1)-括号问题

LC上有非常多很括号相关的问题。比如说有一类是纯括号判断判断一个STRING里的括号是否合法，或者要加最少多少个括号可以使得它合法，或者移除最少多少个括号使得它合法等。
另外一类是基于括号会有一些运算，比如说2（XXX） = XXXXXX 这种decode模式的题目。这个专题我会介绍2个这类问题的本质，帮助你在下次阅读到这类问题，知道如何从本质去思考，然后快速找到问题的突破点。

本质1：括号合法匹配的本质，就是在一个字符串任意前缀里，他的左括号数量必须都大于等于右括号数量。然后最终的字符串左括号数量和右括号数量相等。

本质2 : 括号求表达式的本质，每一个括号内部是一个子问题，我们可以直接把子问题交给递归假设它已解决，然后只要思考如何汇总子问题的解变成全局的解的方法。

1.括号合法匹配的本质

有了本质1的特性，我们再逆向思考，什么时候括号不合法，就可以解决一大类问题了。不合法无非2种。1. 右括号多余左括号了。 2. 到最后左括号还多出了一些，没有被右括号关掉

那么只要维护这2个不合法信息，我就可以知道括号是否合法。
我们只要在遇到做左括号时对L++，右括号时对L--。一旦发现L<0了，就代表右括号多出来了。到最后L！=0就代表左括号没被关掉。

上面是个基础技能。

我们再在基础技能上去衍生一下，看一个不合法的括号情况，如果加上最少的括号使得它合法。这个其实很好想，就是对每一个不合法的括号（分为两类，中间多出来的右括号，和最后没关掉的左括号）

LC. 921 题 就引刃而解

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

下面我们来看一道对偶题。最少移除括号的问题
是LC 1249. Minimum Remove to Make Valid Parentheses

如果只是要求数量的话，上面的代码原封不动就可以用。
这里面需要求一个具体解。这个时候，就要求我们要移除正确的括号了。 如果上面那题增加括号也要一个具体解，小伙伴们想想如何改
其实这边也很好想，凡是要R++的地方，我就跳过这个字母。就解决了中间多出来的右括号问题。然后从后往前再扫一次，凡是遇到左括号，我就直接去掉。就一定可以把没关掉的左括号给关掉了。

这里有些读者会问为什么不可以从左往右的。为什么一定要从右往左呢？

这是因为，你要是从左往右可能是可以，但也可能是移除了一个合法右括号的左半边，引入了新的不合法右括号比如
()(, 你要是从左移除可能会变成)(

那为什么从右往左没这个问题呢？
这里有2个思考角度

• 第一个角度就是，因为所有右括号前必然已经有一个左括号了。还多出来一些左括号，一定是要么在所有右括号后面。那么从右往左就可以WORK，如果是在合法右括号左边。比如((),那么即使你移走了一个左括号，前面多出来的左括号也可以立刻补位。

• 如果有另一个平行宇宙，括号是这样使用的)(, 那么我们就可以在那个平行宇宙 用规则1 去先把多出来的右括号( 给删去。这时就是想只要怎么把这个宇宙的括号规则给映射去那个宇宙，其实就是reverse一下就可以

举个例子( () () ( reverse一下 变成( )( )( (, 记住这个时候(是那个宇宙的右括号了。我们套用规则1，可以发现第一个和最后一个 是多出来的右括号。去掉之后合法括号为)( )(
那么本质这边就是在原宇宙从右向左扫描。

上面那道题代码就如下所示

public String minRemoveToMakeValid(String s) {
        char[] cs = s.toCharArray();
        int l = 0, idx = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == '(') {
                l++;
            } else if (cs[i] == ')') {
                if (l == 0) continue;
                l--;
            }
            cs[idx++] = cs[i];
        }
        int j = cs.length - 1, len = idx - l;
        for (int i = idx - 1; i >= 0; i--) {
            if (l > 0 && cs[i] == '(') l--;
            else cs[j--] = cs[i];
        }
       return new String(cs, j + 1, len);
    }

如果我要最少移除括号的所有可能解，应该如何求呢

我们之前找了数量，然后找了任一解，下面问题如果是所有解，应该怎么求呢？
这就是一道LC HARD问题了。

是LC 301. Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/

这道题其实本质还是找所有可以删除的括号
我们一开始先把不合法的左括号数量和 右括号的数量用之前的套路给统计出来。
如果有不合法右括号，就一定要先从左到向删右括号。因为在右括号被删干净前，左括号一定是不够的。不然就不会出现不合法的右括号，所以在前面删左括号是没必要的。等右括号删干净了。然后之前跳到最后尝试删左括号。
因为答案要去重，所以有连续K个相同格式的括号的情况下只看第一个。这是基本的去重思路了。当然偷懒可以用SET来去重。

List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        char[] cs = s.toCharArray();
        // 统计左右括号不合法数量, l代表左括号不合法数量，r代表右括号不合法数量
        int l = 0, r = 0;
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        dfs(cs, 0, cs.length - 1, l, r, (char)0);
        return new ArrayList<>(res);
    }
    void dfs(char[] cs, int st, int ed, int l, int r, char pre) {
        if (l == 0 && r == 0) {
            String valid = valid(cs);
            if (valid != null)
                res.add(valid);
            return;
        }
        if (st > ed) return;
        if (r > 0) {
            char cur = cs[st];
            if (cur == ')' && pre != ')') {
                cs[st] = 0;
                dfs(cs, st + 1, ed, l, r - 1, cs[st]);
            }
            cs[st] = cur;
            dfs(cs, st + 1, ed, l, r, cur);
        } else { // l > 0
            char cur = cs[ed];
            if (cur == '(' && pre != '(') {
                cs[ed] = 0;
                dfs(cs, st, ed - 1, l - 1, r, cs[ed]);
            }
            cs[ed] = cur;
            dfs(cs, st, ed - 1, l, r, cur);
        }
    }
// 合法的返回结果字符串，不然返回null
    String valid(char[] cs) {
        StringBuilder sb = new StringBuilder();
        int l = 0;
        for (char c : cs) {
            if (c == 0) continue;
            sb.append(c);
            if (c == '(') l++;
            else if (c == ')') {
                if (--l < 0) return null;
            }
        }
        return l > 0 ? null : sb.toString();
    }

当然我们用角度2去写这个题也是可以的
思路为先考虑右括号不合法，再反向考虑左括号不合法。当遇到一个右括号不合法，我们需要枚举之前所有的右括号依次去掉都是解。
然后考虑左括号，可以用平行世界法。

List<String> res = new ArrayList<>();
public List<String> removeInvalidParentheses(String s) {
    dfs(s, 0, '(', ')');
    return res;
}
void dfs(String ans, int lastJ, char L, char R) {
    int l = 0;
    for (int i = 0; i < ans.length(); i++) {
        char c  = ans.charAt(i);
        if (c == L) l++;
        else if (c == R) l--;
        if (l >= 0) continue;
// 枚举之前所有的右括号依次去掉
        for (int j = lastJ; j <= i; j++) {
            if (ans.charAt(j) == R && (j == lastJ || ans.charAt(j - 1) != R))
                dfs(ans.substring(0, j) + ans.substring(j + 1), j, L, R);
        }
        return;
    }
    String rev = new StringBuilder(ans).reverse().toString();
    if (L == '(') dfs(rev,0, R, L); // 去平行宇宙
    else res.add(rev);
}

最后我们来看另一道HARD题，
是LC. 32. Longest Valid Parentheses

这道题，就是要求一个最长的合法括号匹配子串。根据我们的定义知道，只要遇到了不合法的右括号，那么就要和之前的字符串做一个了断了。因为只要包含了这个前缀就不会再合法。那么根据前面的MAX来跟前全局的MAX。之后从头开始。

下一个问题是，如果满足了没有任何前缀有多出来的右括号，我怎么知道这个前缀中最长的合法子串是多少长呢。
所谓合法就是意味着还要满足第二个条件，左右括号数量相等。那么我们就需要特判一下这个条件。

另一个棘手问题是，当左括号>右括号时，我们不知道后面还有没有右括号可以闭起来。这样就会造成一旦之前有个多出来的左括号，第二个条件始终没法满足。但是去掉这个多出来的左括号，是可以造成后面满足条件的。解决这个问题，就是从右向左再找一遍，就可以规避掉最前面的左括号捣乱了。这时就是个平行宇宙的概念。

代码如下

public int longestValidParentheses(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        return Math.max(help(s, '(', ')'), help(rev, ')', '('));
    }
    int help(String s, char L, char R) {
        int leftCnt = 0, rightCnt = 0, res = 0;
        for (char c : s.toCharArray()) {
            if (c == L) leftCnt++;
            else rightCnt++;
            if (leftCnt == rightCnt) res = Math.max(res, 2 * leftCnt);
            else if (rightCnt > leftCnt) {
                rightCnt = leftCnt = 0;
            }
        }
        return res;
    }

LC上还有一道题是带通配符的括号是否匹配

LC 678. Valid Parenthesis String。

其实就是说*既可以被当做左括号或者右括号或者空白字符。看这个字符串是否匹配。
其实本质就是在维护括号匹配的2大特性。如果当中出现了右括号不合法，我们就看之前的通配符用作左括号。如果最后是左括号多出来了，我们就维护一个变量，尽可能压缩之前的左括号。
所以我们就有了一个容错区间，LMIN是防止左括号用不完的情况所以代表，只要左括号多出来了，我来一个通配符我都当它是右括号。 LMAX代表，希望左括号越多越好，这样万一后面来了很多右括号，我也有很多储备尽可能不被击穿。

public boolean checkValidString(String s) {
    int lmax = 0, lmin = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            lmax++; lmin++;
        } else if (c == ')') {
            lmax--; 
            lmin = Math.max(0, lmin - 1);
            if (lmax < 0) return false; // 储备也被右括号击穿了，就彻底不合法
        } else { // 通配符，提升储备同时防止左括号过多
            lmax++;
            lmin = Math.max(0, lmin - 1);
        }
    }
    return lmin == 0; // 尽可能的消耗左括号还是消耗不完，不合法
}

2.括号求表达式的本质

在讲这个问题之前，我们先来思考一个非常简单的问题，就是求二叉树的深度。一般二叉树的问题，很多都可以用递归来解决。我们在思考的时候，就是让左子树返回一些信息，同时让右子树范围一些信息。父节点就根据左右子树返回的信息做一些处理，再返回。这就是二叉树里递归的思想。

其实在解决一些表达式计算的时候，是和二叉树递归有很多类似的地方。基本都可以转换过去。而思维的突破点就是如果定义叶子节点，内部节点如何根据叶子结算得到值返回给上层。这2个思考点。

我们来看一道题
LC. 856. Score of Parentheses
这道题，其实() 就是叶子节点，他的分数为1分。
内部节点其实就是外层的括号，他的函数就是对他的孩子节点返回的值求和 然后再乘以2.
所以一个这样的表达式可以画成如下的树((()())())
这里整个表达式 是个根节点。

image.png
大方向是这样，具体的写法可以有很多种。比如这种乘以2的算子是可以下推的，所以我们就可以不用构建这个树。而是在叶子节点的时候，直接把父亲节点们下推的算子全部作用上，然后加到RESULT里即可。这样可以把时间复杂度从O(N^2) 优化到 O(N)
因为前者，我们需要找到每一个左括号匹配的对应右括号，然后递归去算。那么递归里每一层都是O(N)，最坏情况下是O(N ^2)
我们看下算子下推的写法

public int scoreOfParentheses(String S) {
    int depth = 0, res = 0;
    char[] cs = S.toCharArray();
    for (int i = 0; i < cs.length; i++) {
        if (cs[i] == '(') depth++;
        else {
            depth--;
            if (cs[i - 1] == '(') 
                res += 1 << depth; // 叶子节点，把父亲们积累的DEPTH一次作用上
        }
    }
    return res;
}

有了这个思路，我们再来看另2道题。
一道是394. Decode String
另一道是1190. Reverse Substrings Between Each Pair of Parentheses
在这类题目里，叶子节点就是括号里面不带括号的STRING。而外层的括号，就是内部节点。在第一题中，我们可以构建的树长成下图。

我们以2[b2[c]]3[a]为例子

image.png

在第二个问题里
我们以(u(love)i)为例子

image.png

在这类问题里，我们可以使用一个stack,然后用后序遍历的方式来计算。因为每个节点最后返回的是一个STRING，所以我们可以在STACK里存的是STRINGBUILDER，那么返回的时候TOSTRING即可。
当我们遇到一个左括号，我们推入栈一个STRINGBUILDER，然后之后的操作就是在栈顶的STRINGBUILDER里做，直到遇到右括号，然后把STRINGBUILDER 弹出之后，就是在父节点那层获得了孩子节点做完的返回的信息，然后加入到父节点的STRINGBUILDER（在栈顶了）中计算。
所以2道题差不多，代码如下
第一题对每个节点，除了要维护STRING，还要维护乘法系数，所以需要2个栈

public String decodeString(String s) {
    char[] cs = s.toCharArray();
    Deque<Integer> nums = new ArrayDeque<>();
    Deque<StringBuilder> sbs = new ArrayDeque<>();
    sbs.push(new StringBuilder());
    int num = 0;
    StringBuilder sb = new StringBuilder();
    for (char c : cs) {
        if (c == '[') {
            nums.push(num);
            sbs.push(new StringBuilder());
            num = 0;
        } else if (c == ']') {
            int cnt = nums.pop();
            String cur = sbs.pop().toString();
            for (int i = 0; i < cnt; i++) {
                sbs.peek().append(cur);
            }
        } else if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else {
            sbs.peek().append(c);
        }
    }
    return sbs.peek().toString();
}

第二题就是出栈的时候需要做一个REVERSE

public String reverseParentheses(String s) {
        Deque<StringBuilder> stk = new ArrayDeque<>();
        stk.push(new StringBuilder());
        for (char c : s.toCharArray()) {
            if (c == '(') stk.push(new StringBuilder());
            else if (c == ')') {
                String res = stk.pop().reverse().toString();
                stk.peek().append(res);
            } else stk.peek().append(c);
        }
        return stk.peek().toString();
    }

第二题有一个O(N)的解法，由于解法和本章无关，所以没有介绍，有兴趣的小伙伴可以去DISCUSS里学习。

上面的题目，节点的定义和节点的计算都是比较简单直观的。一般LC HARD的题，就会稍微复杂一些。我找到了如下3题。

726. Number of Atoms
727. Parse Lisp Expression
728. Brace Expansion II

对726题来说
每一个括号里我们需要统计元素的个数，所以需要返回一个MAP作为信息，返回到上层后，还需要乘以系数，加入父节点的MAP里。因为最后需要按照字母序排序，所以使用TREEMAP即可。

public String countOfAtoms(String formula) {
        Map<String, Integer> m = help(formula.toCharArray());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            sb.append(e.getKey());
            if (e.getValue() > 1) sb.append(e.getValue());
        }
        return sb.toString();
    }
    int i = 0;
    private Map<String, Integer> help(char[] cs) {
        Map<String, Integer> m = new TreeMap<>();
        while (i < cs.length) {
            if (cs[i] == '(') {
                i++;
                // 拿孩子节点的信息
                Map<String, Integer> chd = help(cs);
                // 拿系数
                int num = 0;
                while (i < cs.length && Character.isDigit(cs[i])) num = num * 10 + cs[i++] - '0';
                for (Map.Entry<String, Integer> e : chd.entrySet()) {
                    String key = e.getKey(); 
                    int val = num * e.getValue();
                    m.compute(key, (k,v)->{
                        if (v == null) return val;
                        return v + val;
                    });
                }
            } else if (cs[i] == ')') {
                i++;
                break; // 本节点MAP处理完毕
            } else {
                // 处理子叶子节点
                StringBuilder sb = new StringBuilder(""+cs[i++]);
                while (i < cs.length && cs[i] >= 'a' && cs[i] <= 'z') 
                    sb.append(cs[i++]);
                int num = 0;
                while (i < cs.length && Character.isDigit(cs[i])) num = num * 10 + cs[i++] - '0';
                int val = Math.max(1, num);
                m.compute(sb.toString(), (k,v)->{
                    if (v == null) return val;
                    return v + val;
                });
            }
        }
        return m;
    }

我们再来看736题
736题对于一个树节点来说，就是用括号括起来的运算，里面可能包括子运算。最后返回的是一个整数。节点有3种类型分别是ADD, MULT, LET。
而叶子节点就是一个纯数字。为什么这么定义呢？因为我们发现5 和 （add 2 3）是可以等价的。所以纯数字是可以定义为叶子节点。
然后进一步分析，ADD, MULT是内部节点的时候，会有2个孩子。而LET可能有多个孩子。
如果内部节点是LET，其之后的结构必然是一个变量加一个子节点。（子节点可能是叶子节点，可能是需要递归计算的内部节点），最后一个子节点为LET的返回值。同时上层LET的变量表需要透传到其孩子节点中。
所以大概的树结构如下
以(let x 2 (mult x (let x 3 y 4 (add x y))))为例

image.png

public int evaluate(String exp) {
    // hashmap 需要下传
    return eval(exp, new HashMap<>());
}
private int eval(String exp, Map<String, Integer> vals) {
    // 如果没有以括号开头，那么是叶子节点
    if (exp.charAt(0) != '(') {
        if (exp.charAt(0) == '-' || Character.isDigit(exp.charAt(0))) { // 纯数字
            return Integer.parseInt(exp);
        } else { // 变量值
            return vals.get(exp);
        }
    }
    // 以括号开头，处理内部节点，后面操作后的参数按照空格切割。
    List<String> exps = parse(exp);
    // 继承父亲的MAP，构建自己这层的MAP
    Map<String, Integer> curVals = new HashMap<>(vals);
    if (exp.startsWith("(a")) { // 如果是加法，递归2个孩子
        return eval(exps.get(0), curVals) + eval(exps.get(1), curVals);
    } else if (exp.startsWith("(m")) { // 如果是乘法，递归2个孩子
        return eval(exps.get(0), curVals) * eval(exps.get(1), curVals);
    } else { // 如果是LET，递归（SIZE / 2） 个孩子
        for (int i = 1; i < exps.size() - 1; i += 2) {
            curVals.put(exps.get(i - 1), eval(exps.get(i), curVals));
        }
        // 最后一个作为返回值
        return eval(exps.get(exps.size() - 1), curVals);
    }
}
List<String> parse(String curExp) {
    int st = curExp.startsWith("(m") ? 6 : 5;
    curExp = curExp.substring(st);
    char[] cs = curExp.toCharArray();
    int left = 1, i = 0, pre = 0;
    List<String> res = new ArrayList<>();
    for (;left > 0; i++) { // 只关心本层的括号 和直接变量； 遇到上层括号，循环退出
        if (cs[i] == '(') left++;
        else if (cs[i] == ')') { 
            if (left-- == 1) res.add(curExp.substring(pre, i));
        } else if (left == 1 && cs[i] == ' ') {
            res.add(curExp.substring(pre, i));
            pre = i + 1;
        }
    }
    return res;
}

最后一道题1096

我们可以把{}里的值当做内部节点，纯字母当做叶子节点。
然后内部节点返回的是LIST<STRING>， 那么纯字母返回的其实就是只含一个STRING的LIST。
在外层父节点，根据孩子节点的信息做计算。
父节点可以做2种运算，distinct union或者对2个集合做笛卡尔乘积。这取决于节点之间是否有逗号。
那么构建树，如下图
以"{{a,z},a{b,c},{ab,z}}"为例

image.png
所以这递归函数中，遇到左括号，调用递归，拿到孩子的信息，把这个信息放入，自己的处理队列中。遇到逗号，就之前积攒的东西，放进SET里去做DISTINCT UNION。遇到右括号，代表自己这个节点使命结束，退出来之后，对所有队列的东西做笛卡尔积然后DISTINCT UNION返回给上层。

int i = 0;
public List<String> braceExpansionII(String expression) {
    String e = "{" + expression + "}";
    return help(e.toCharArray());
}
List<String> help(char[] cs) {
    assert cs[i++] == '{';
    List<List<String>> pre = new ArrayList<>();
    TreeSet<String> set = new TreeSet<>();
    while (i < cs.length) {
        if (cs[i] == ',') {
            // 求之前进预备队列的笛卡尔积，然后放进DISTINCT UNION
            set.addAll(combine(pre));
            pre = new ArrayList<>();
            i++;
        } else if (cs[i] == '{') {
             // 把孩子的返回，放进笛卡尔积预备队列里
            pre.add(help(cs));
        } else if (cs[i] == '}') break;
        else {
            // 叶子节点
            StringBuilder sb = new StringBuilder();
            while (Character.isLowerCase(cs[i])) {
                sb.append(cs[i++]);
            }
            pre.add(Arrays.asList(sb.toString()));
        }
    }
    assert cs[i++] == '}';
    // 最后把余下的预备队列里的数计算完，放进DISTINCT UNION中
    set.addAll(combine(pre));
    return new ArrayList<>(set);
}
private List<String> combine(List<List<String>> in) {
    List<String> res = Arrays.asList("");
    for (List<String> i: in) {
        List<String> tmp = res;
        res = new ArrayList<>();
        for (String pre : tmp) {
            for (String post : i) {
                res.add(pre + post);
            }
        }
    }
    return res;
}

总结

今天我们主要讲解了2种括号的套路和思维方式。

• 第一种就是依靠括号匹配2个特性来找到突破点去解题。特性1是任意前缀左括号数量大于右括号，特性2最终左括号右括号数量相等。
• 第二种就是定义出叶子节点和内部节点的计算单元，找出每个单元的返回的数据结构，然后思考如何利用孩子的解取组合出父亲的解。

最后给大家留一道思考题。之前我们只讨论了一种括号的合法匹配。如果括号有3种，{},[],()。 且前者可以包含后者，后者不能包含前者，如果判断括号是匹配的呢。如果不匹配最少删除多少个使之匹配呢？