LC上有非常多很括号相关的问题。比如说有一类是纯括号判断判断一个STRING里的括号是否合法，或者要加最少多少个括号可以使得它合法，或者移除最少多少个括号使得它合法等。
另外一类是基于括号会有一些运算，比如说2（XXX） = XXXXXX 这种decode模式的题目。这个专题我会介绍2个这类问题的本质，帮助你在下次阅读到这类问题，知道如何从本质去思考，然后快速找到问题的突破点。
本质1：括号合法匹配的本质，就是在一个字符串任意前缀里，他的左括号数量必须都大于等于右括号数量。然后最终的字符串左括号数量和右括号数量相等。
本质2 : 括号求表达式的本质，每一个括号内部是一个子问题，我们可以直接把子问题交给递归假设它已解决，然后只要思考如何汇总子问题的解变成全局的解的方法。
有了本质1的特性，我们再逆向思考，什么时候括号不合法，就可以解决一大类问题了。不合法无非2种。1. 右括号多余左括号了。 2. 到最后左括号还多出了一些，没有被右括号关掉
那么只要维护这2个不合法信息，我就可以知道括号是否合法。
我们只要在遇到做左括号时对L++，右括号时对L--。一旦发现L<0了，就代表右括号多出来了。到最后L！=0就代表左括号没被关掉。
上面是个基础技能。
我们再在基础技能上去衍生一下，看一个不合法的括号情况，如果加上最少的括号使得它合法。这个其实很好想，就是对每一个不合法的括号（分为两类，中间多出来的右括号，和最后没关掉的左括号）
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个思考点。
我们来看一道题
LC. 856. Score of Parentheses
这道题，其实() 就是叶子节点，他的分数为1分。
内部节点其实就是外层的括号，他的函数就是对他的孩子节点返回的值求和 然后再乘以2.
所以一个这样的表达式可以画成如下的树((()())())
这里整个表达式 是个根节点。
大方向是这样，具体的写法可以有很多种。比如这种乘以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]为例子
在第二个问题里
我们以(u(love)i)为例子
在这类问题里，我们可以使用一个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题。
-
Number of Atoms
-
Parse Lisp Expression
-
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))))为例
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;
}
我们可以把{}里的值当做内部节点，纯字母当做叶子节点。
然后内部节点返回的是LIST， 那么纯字母返回的其实就是只含一个STRING的LIST。
在外层父节点，根据孩子节点的信息做计算。
父节点可以做2种运算，distinct union或者对2个集合做笛卡尔乘积。这取决于节点之间是否有逗号。
那么构建树，如下图
以"{{a,z},a{b,c},{ab,z}}"为例
所以这递归函数中，遇到左括号，调用递归，拿到孩子的信息，把这个信息放入，自己的处理队列中。遇到逗号，就之前积攒的东西，放进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种，{},[],()。 且前者可以包含后者，后者不能包含前者，如果判断括号是匹配的呢。如果不匹配最少删除多少个使之匹配呢？