往上加运算符也好，加括号也好，删除括号也好，最稳妥的方式都是 带 StringBuilder 从头扫的 DFS + Backtracking.
在没有任何优先级后顾之忧的情况下，可以以操作符为分界线，Divide & Conquer. 否则得存每个 subproblem 的前后缀用于做 join.
有乘法优先级顾虑时，需要在 dfs 参数里传上一次操作的值，用于恢复和重新计算；连续多个乘法可以自动叠加。
在只有一种括号的情况下，维护 left / right count 就可以 one-pass 知道到底有几个 left / right 括号没正确匹配
Dijkstra 的 Shunting-Yard 算法是生成 RPN 的大杀器，也是 calculator 类问题的通解。
先说一个自己的做法，写的是搜索，对于每一个 input string ，我们扫描并建立两个 list; 一个是 operands，一个是 operators. 每次 dfs 的时候挑一对数字和一个操作符，计算，修改 list 做 dfs，返回之后再把 list 改回来。
过了 15/25 个 test case 之后卡在了 "2*3-4*5" 上面，原因是多了一个额外的 -14，因为两个 subproblem 加括号的方式是一样的，顺序不同而已。
所以暴力搜索的问题在于，如果前面和后面加括号的方式是一样的，需要额外手段来判断 “重复” 。
而DFS 中想 cache 一个 List<>，远远不如 String 方便。
如果实在追求暴力到底，就干脆对每一个状态都搞序列化，记录当前的 operands & operators ，遇到重复的状态就直接返回了。
因此为了避免 dfs + backtracking 可能遇到的 overlap subproblem 返回多个结果的问题，可以先直接 divide & conquer，因为这个搜索结构是树状的，天生的 disjoint.
根据这个思想，我们可以以“操作符”为分隔，借鉴编译器和 reverse polish notation 中的 "expression tree" 来进行计算，结构如下：
这样左右子树都进行的完美的分隔，而且应为 input 为 string ，也非常容易对子问题进行记忆化搜索。
Divide & Conquer, 8ms，超过 41.50%.
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> rst = new ArrayList<>();
for(int i = 0; i < input.length(); i++){
if(!Character.isDigit(input.charAt(i))){
char operator = input.charAt(i);
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for(int num1 : left){
for(int num2 : right){
if(operator == '+') rst.add(num1 + num2);
if(operator == '-') rst.add(num1 - num2);
if(operator == '*') rst.add(num1 * num2);
}
}
}
}
if(rst.size() == 0) rst.add(Integer.parseInt(input));
return rst;
}
}
带记忆化搜索，3ms，超过 91.61%
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
return helper(input, new HashMap<String, List<Integer>>());
}
private List<Integer> helper(String str, HashMap<String, List<Integer>> map){
if(map.containsKey(str)) return map.get(str);
List<Integer> list = new ArrayList<>();
for(int i = 0; i < str.length(); i++){
char chr = str.charAt(i);
if(!Character.isDigit(chr)){
List<Integer> leftList = helper(str.substring(0, i), map);
List<Integer> rightList = helper(str.substring(i + 1), map);
for(int leftNum : leftList){
for(int rightNum : rightList){
if(chr == '+') list.add(leftNum + rightNum);
if(chr == '-') list.add(leftNum - rightNum);
if(chr == '*') list.add(leftNum * rightNum);
}
}
}
}
if(list.size() == 0) list.add(Integer.parseInt(str));
map.put(str, list);
return list;
}
}
首先最容易想到的是 naive 的 O(n^2) 解法，即以每一个 '(' 为起点向右扫，看到 '(' count ++，看到 ')' count -- ，什么时候 count = 0 代表当前 substring 是有效的，count 为负则直接 break.
注意这招只在只有一种括号的时候有效，不能用来做 "Valid Parentheses"，会在 "([)]" 这种 test case 上挂掉。
显然，因为时间复杂度过高这么写不能 AC，因为重复扫描实在太多了。
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int max = 0;
for(int i = 0; i < n; i++){
char chr = s.charAt(i);
if(chr == '('){
int count = 1;
int ptr = i + 1;
while(ptr < n){
if(s.charAt(ptr) == '(') count ++;
if(s.charAt(ptr) == ')') count --;
if(count == 0) max = Math.max(max, ptr - i + 1);
if(count < 0) break;
ptr ++;
}
}
}
return max;
}
}
仔细思考一下我们如何定义 "Valid Parenthese"，还有他们都长什么样。
Valid Parenthese 只有可能是这两种情况；
以一对括号为 "kernel" ，向外扩散的，如 ((()))
多个 "kernel" 扩张出现，相互连续的，如 (())()(())
参考了 LC 论坛的一种解法，非常巧妙，利用了这样的一个隐藏性质：
用 Stack 做常规括号匹配，字符串扫描完毕之后，还存留在 Stack 中的 index 都是无法匹配的字符。
如果字符串正常从左向右扫的话，这个 Stack 中的元素 index 还是排好序的，元素 index 之间的 gap，就代表着可以匹配的括号。
同时要注意考虑字符串最两端作为起点和终点的可能性，用最右端做初始化，用最左端做收尾。
于是就有了下面这个 O(n) 的代码，空间复杂度为 O(n / 2);
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(') stack.push(i);
else if(!stack.isEmpty() && s.charAt(stack.peek()) == '(') stack.pop();
else stack.push(i);
}
// Whole string is matched
//if(stack.isEmpty()) return s.length();
int rightEnd = s.length();
int max = 0;
while(!stack.isEmpty()){
int cur = stack.pop();
max = Math.max(max, rightEnd - cur - 1);
rightEnd = cur;
}
max = Math.max(max, rightEnd);
return max;
}
}
另一种解法是用 DP，空间占用大一倍，但是速度快，思路上非常接近于 Palindrome Partitioning.
dp[i] = 以 i 结尾的括号的最长 valid parenthese 长度
先读 dp[i - 1] 的长度，然后根据长度找到最左面的目标位置 leftPos，看看是不是 '('，如果是，就可以 dp[i] = dp[i - 1] + 2 了，代表可以连续构造；
另一种情况是多个独立的括号序列相邻，所以每次如果当前位置可以构造括号，要再找一下 dp[leftPos - 1] 的长度，把相邻序列串起来。
速度超过85.05% ~
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int[] dp = new int[n]; // dp[i] = Maximum valid parentheses length ends with i
dp[0] = 0;
int max = 0;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) == ')'){
int len = dp[i - 1];
int leftPos = i - len - 1;
if(leftPos >= 0 && s.charAt(leftPos) == '(') {
dp[i] = dp[i - 1] + 2;
if(leftPos - 1 >= 0) dp[i] += dp[leftPos - 1];
} else {
dp[i] = 0;
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
(FB) 简化版，Remove Invalid Parenthese
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"
简单说，就是在尽量保留有效括号的情况下，返回任意一种正确结果。
在只有一种括号的时候，是可以扫一遍通过 +/- 来找出非法括号的，不过以一个方向定义的 +/- 只能找出一种，需要两个方向都扫一遍。
"(" 为正 , ")" 为负 ，从左向右可以找到非法的 ')'
")" 为正，"(" 为负，从右向左可以找到非法的 '('
后面的就非常 trivial 了。
private static String removeInvalid(String str){
char[] chrArr = str.toCharArray();
int val = 0;
for(int i = 0; i < chrArr.length; i++){
if(chrArr[i] == '(') val ++;
else if(chrArr[i] == ')') val --;
if(val < 0) {
chrArr[i] = '#';
val = 0;
}
}
val = 0;
for(int i = chrArr.length - 1; i >= 0; i--){
if(chrArr[i] == ')') val ++;
else if(chrArr[i] == '(') val --;
if(val < 0){
chrArr[i] = '#';
val = 0;
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < chrArr.length; i++){
if(chrArr[i] != '#') sb.append(chrArr[i]);
}
return sb.toString();
}
public static void main(String[] args) {
String[] testcases = new String[]{"()()()()((()()())()(",
"()AD(S)A()W)(S))()ASD()",
"))ASDAS()()()Q(((())QWE)()",
"S()((A)()D))W)Q())(EQ())()W(",
"))ASD)QW(()S(Q)(WE)(Q()(AS)D("};
for(int i = 0; i < testcases.length; i++){
System.out.println("Input : " + testcases[i]);
System.out.println("Output : " + removeInvalid(testcases[i]));
System.out.println();
}
}
这题的结构就和 Different ways to add parenthese 不一样，括号之间的相对位置是非常重要的，而且有连续性，不能像那题一样直接在操作符上建一个 expression tree 出来，divide & conquer.
首先继承上一题 Stack 的经验，我们很容易可以知道需要的最少 edit 次数，以及 invalid 字符位置：跑一遍算法，看 Stack 里剩几个元素，分别在哪就行了。
只有一个非法括号的情况：
( ( ) ) ( ) '(' ( ( ) ) ( )
可以发现对于 '(' ，只能向右删下一个 '('，相邻的 '(' 是重复解
( ) ( ( ) ) ')' ( ) ( ( ) )
同理，')' 只能往左边找')'，相邻 ')' 为重复解。
有两个非法括号的情况：
( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )
( ) ( ( ) ) ( ) ( ( ) ) ( )
( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )
可以发现 ')' 有两个可能的位置，'(' 有两个可能的位置，于是是 4 种组合。
于是这题就变成了一个搜索问题~
问题1：既然在反复在字符串上进行修改，如何还能保证 List<> 里面的非法字符位置还是正确的？
问题2：动态修改的 string ，动态变化的 index，要处理很多细节保证他们的 match.
觉得顺着这个思路越想细节越多。。于是参考了下论坛的 DFS 思路，在所有 DFS 解法中，我最喜欢这个，非常简洁易懂，而且不依赖什么 trick，便于和面试官交流。
先扫一遍原 string ，记录下需要移除的左括号数量和右括号数量，保证最后的解最优；
于是开始 DFS，对于每一个新的字符，我们都有两个选择：'留' 或者 '不留'，就像二叉树的分叉一样，留下了 dfs + backtracking 的空间。
于是当我们针对各种情况进行 dfs 的时候，我们一定可以考虑到所有可能的有效 path，接下来需要定义什么是 “有效 path”
base case 是左右括号和开括号数量都为零，并且 index 读取完了所有字符，则把结果添加进去；
如果在任何时刻，左右括号和开括号的数量为负，我们都可以直接剪枝返回。
这种解法的主要优点是好理解，空间上因为只用了一个 StringBuilder 非常经济，相比 BFS 速度和空间上都优异很多。如果说进一步优化的空间在哪，那就是对于 “重复状态” 的缓存与记忆化搜素还有提高的空间。
于是很 naive 的尝试了下加入 Set<> 来记录已经访问过的 StringBuilder 状态试图剪枝，然而很容易就出了 “没有任何返回结果” 的 bug ，其原因是，这个 dfs + backtracking 的代码本来就是在一个神似 binary tree 的结构上做一个 dfs 穷举而已，并不是 top-down recursion 那种子问题覆盖的结构，所以不适合用记忆化搜索解决。非要用的话至少 dfs 的返回类型就不能是 void ，至少也得是个 List<> 或者 Set<> 之类的 “子问题结果” 嘛。
public class Solution {
public List<String> removeInvalidParentheses(String s) {
Set<String> set = new HashSet<>();
int leftCount = 0;
int rightCount = 0;
int openCount = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(') leftCount++;
if(s.charAt(i) == ')'){
if(leftCount > 0) leftCount--;
else rightCount ++;
}
}
dfs(set, s, 0, leftCount, rightCount, openCount, new StringBuilder());
return new ArrayList<String>(set);
}
private void dfs(Set<String> set, String str, int index, int leftCount,
int rightCount, int openCount, StringBuilder sb){
if(index == str.length() && leftCount == 0 && rightCount == 0 && openCount == 0){
set.add(sb.toString());
return;
}
if(index == str.length() || leftCount < 0 || rightCount < 0 || openCount < 0) return;
char chr = str.charAt(index);
int len = sb.length();
if(chr == '('){
// Remove current '('
dfs(set, str, index + 1, leftCount - 1, rightCount, openCount, sb);
// Keep current '('
dfs(set, str, index + 1, leftCount, rightCount, openCount + 1, sb.append(chr));
} else if(chr == ')'){
// Remove current ')'
dfs(set, str, index + 1, leftCount, rightCount - 1, openCount, sb);
// Keep current ')'
dfs(set, str, index + 1, leftCount, rightCount, openCount - 1, sb.append(chr));
} else {
// Just keep the character
dfs(set, str, index + 1, leftCount, rightCount, openCount, sb.append(chr));
}
// Back-tracking
sb.setLength(len);
}
}
参考论坛思路的一个 BFS 写法，速度很慢只能超过 14%，搞的有点像 word ladder 了。。。 不过另一个好处是，既然这么高的时间复杂度都能过，我那个 dfs 的解法也不用太追求完美，这样 index offset 的问题更好解决，遇到个新 string 直接重扫就好了。
public List<String> removeInvalidParentheses(String s) {
List<String> rst = new ArrayList<>();
if(isValid(s)){
rst.add(s);
return rst;
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
boolean isFound = false;
visited.add(s);
queue.offer(s);
while(!queue.isEmpty() && !isFound ){
int size = queue.size();
for(int i = 0; i < size; i++){
String str = queue.poll();
for(int pos = 0; pos < str.length(); pos++){
StringBuilder sb = new StringBuilder(str);
sb.deleteCharAt(pos);
String next = sb.toString();
if(visited.contains(next)) continue;
if(isValid(next)){
isFound = true;
rst.add(next);
} else {
queue.offer(next);
}
visited.add(next);
}
}
}
return rst;
}
private boolean isValid(String s){
if(s == null || s.length() == 0) return true;
int count = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(') count++;
if(s.charAt(i) == ')') count--;
if(count < 0) return false;
}
return (count == 0);
}
num = "105", target = 5;
返回 ["10-5", "1x0+5", "1+0x5", "1x05", "1-0x5"] 是错的
在 Different ways to add parentheses 里，这么干没有任何问题，因为默认是加括号的，左右子树可以完全分离，单独求值。
而这题里，用 divide & conquer 无可避免地遇到符号优先级问题。于是看了一圈 LC 论坛，大家的做法其实都是 DFS + backtracking ..
这题非要用 divide & conquer 也不是不行，但是极其麻烦，如图所示：
对于每一个节点，我们需要考虑其左子树的 String, value，还有抹去最后一步运算的 String 与 value .. 对于右子树，我们还需要其抹去第一步运算的 String 与 value 才能正确做 join.
所以说，珍爱生命，有乘法就远离 divide & conquer 吧。
流程：
dfs 函数中存 "左面表达式的当前值" 和 "上一步操作的结果" (用于处理优先级)
参数都用 Long，防止溢出，毕竟 String 可能是个大数
如果 start 位置是 0 而且当前循环的 index 还是 0，直接 return，因为一轮循环只能取一次 0；
start == 0 的时候，直接考虑所有可能的起始数字扔进去，同时更新 cumuVal 和 prevVal;
除此之外，依次遍历所有可能的 curVal parse，按三种不同的可能操作做 dfs + backtracking;
加法：直接算，prevVal 参数传 curVal，代表上一步是加法；
减法：直接算，prevVal 参数传 -curVal，代表上一步是减法；
乘法：要先减去 prevVal 抹去上一步的计算，然后加上 prevVal curVal 代表当前值；同时传的 preVal 参数也等于 prevVal curVal.
乘法操作这种处理方式，在遇到连续乘法的时候可以看到是叠加的；但是前一步操作如果不是乘法，则可以优先计算乘法操作。
10-5-2x6 ，遇到乘法之前是 cumuVal = 3, preVal = -2; 新一轮 dfs 时 curVal = 6, 先退回前一步操作 - prevVal，得到 5，其实就是之前 (10 - 5) 的结果，然后加上当前结果 (-2 x 5)，prevVal 设成 -10 传递过去即可。
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> rst = new ArrayList<>();
dfs(rst, new StringBuilder(), num, target, 0, 0, 0);
return rst;
}
private void dfs(List<String> rst, StringBuilder sb, String num, int target, int startPos, long cumuVal, long prevVal){
if(startPos == num.length() && cumuVal == target){
rst.add(sb.toString());
return;
}
for(int i = startPos; i < num.length(); i++){
// We can pick one zero to start with; but not multiple
if(num.charAt(startPos) == '0' && i != startPos) return;
int len = sb.length();
String curStr = num.substring(startPos, i + 1);
long curVal = Long.parseLong(curStr);
if(startPos == 0){
dfs(rst, sb.append(curVal), num, target, i + 1, curVal, curVal);
sb.setLength(len);
} else {
dfs(rst, sb.append("+" + curStr), num, target, i + 1, cumuVal + curVal, curVal);
sb.setLength(len);
dfs(rst, sb.append("-" + curStr), num, target, i + 1, cumuVal - curVal, -curVal);
sb.setLength(len);
dfs(rst, sb.append("*" + curStr), num, target, i + 1, cumuVal - prevVal + prevVal * curVal, prevVal * curVal);
sb.setLength(len);
}
}
}
}
数字可能是多数位的，也可能是0，不能 assume 都是一位数；
复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。
建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；
如果看到数字，直接添加到 StringBuilder 中；
如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；
如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。
public class Solution {
public int calculate(String s) {
// "(10+( 14+25+2)-0)+(0+18)"
// multiple digits;
// number zero;
// have spaces;
return solveRPN(getRPN(s));
}
// "123 \s 23 \s + \s 45 \s - \s 44 ..."
private String getRPN(String s){
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
char chr = s.charAt(i);
if(chr == ' ') continue;
if(Character.isDigit(chr)){
sb.append(chr);
} else {
sb.append(' ');
if(chr == '('){
stack.push(chr);
} else if (chr == ')'){
while(!stack.isEmpty() && stack.peek() != '('){
sb.append(stack.pop());
sb.append(' ');
}
stack.pop();
} else {
// is "+" or "-" operator with same precedence level
while(!stack.isEmpty() && stack.peek() != '('){
sb.append(stack.pop());
sb.append(' ');
}
stack.push(chr);
}
}
}
while(!stack.isEmpty()){
sb.append(' ');
sb.append(stack.pop());
}
return sb.toString();
}
private int solveRPN(String s){
String[] strs = s.split(" ");
Stack<Integer> stack = new Stack<>();
for(String str : strs){
if(str.equals("")) continue;
if("+-".indexOf(str) != -1){
int num2 = stack.pop();
int num1 = stack.pop();
if(str.equals("+")) stack.push(num1 + num2);
if(str.equals("-")) stack.push(num1 - num2);
} else {
stack.push(Integer.parseInt(str));
}
}
return stack.pop();
}
}
Shunting Yard Algorithm 的做法同上，加一个优先级就行。
public class Solution {
public int calculate(String s) {
return evalRPN(getRPN(s));
}
private String getRPN(String s){
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
char chr = s.charAt(i);
if(chr == ' ') continue;
if(Character.isDigit(chr)){
sb.append(chr);
} else {
sb.append(' ');
if(chr == '('){
stack.push(chr);
} else if(chr == ')'){
while(stack.peek() != '('){
sb.append(stack.pop());
sb.append(' ');
}
stack.pop();
} else {
while(!stack.isEmpty() && getPrecedence(chr) <= getPrecedence(stack.peek())){
sb.append(stack.pop());
sb.append(' ');
}
stack.push(chr);
}
}
}
while(!stack.isEmpty()){
sb.append(' ');
sb.append(stack.pop());
}
return sb.toString();
}
private int evalRPN(String s){
String[] strs = s.split(" ");
Stack<Integer> stack = new Stack<>();
for(String str : strs){
if(str.equals("")) continue;
// Is operator
if("+-*/".indexOf(str) != -1){
int num2 = stack.pop();
int num1 = stack.pop();
if(str.equals("+")) stack.push(num1 + num2);
if(str.equals("-")) stack.push(num1 - num2);
if(str.equals("*")) stack.push(num1 * num2);
if(str.equals("/")) stack.push(num1 / num2);
} else {
stack.push(Integer.parseInt(str));
}
}
return stack.pop();
}
private int getPrecedence(char chr){
if(chr == '*' || chr == '/') return 3;
if(chr == '+' || chr == '-') return 2;
return 0;
}
}
