括号与数学表达式的计算

往上加运算符也好，加括号也好，删除括号也好，最稳妥的方式都是 带 StringBuilder 从头扫的 DFS + Backtracking.

在没有任何优先级后顾之忧的情况下，可以以操作符为分界线，Divide & Conquer. 否则得存每个 subproblem 的前后缀用于做 join.

有乘法优先级顾虑时，需要在 dfs 参数里传上一次操作的值，用于恢复和重新计算；连续多个乘法可以自动叠加。

在只有一种括号的情况下，维护 left / right count 就可以 one-pass 知道到底有几个 left / right 括号没正确匹配

Dijkstra 的 Shunting-Yard 算法是生成 RPN 的大杀器，也是 calculator 类问题的通解。

Different Ways to Add Parentheses

先说一个自己的做法，写的是搜索，对于每一个 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;
    }
}

Longest Valid Parentheses

首先最容易想到的是 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] = 0;

  • 对于 ')' ，就需要计算一下了。

• 先读 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

http://www.1point3acres.com/bbs/thread-192179-1-1.html

"(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();
        }
    }

Remove Invalid Parentheses

这题的结构就和 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);
    }

Expression Add Operators

num = "105", target = 5;

返回 ["10-5", "1x0+5", "1+0x5", "1x05", "1-0x5"] 是错的

• 不应该直接把 "05" 当成数字；

• 乘法符号有优先级问题。

在 Different ways to add parentheses 里，这么干没有任何问题，因为默认是加括号的，左右子树可以完全分离，单独求值。

而这题里，用 divide & conquer 无可避免地遇到符号优先级问题。于是看了一圈 LC 论坛，大家的做法其实都是 DFS + backtracking ..

这题非要用 divide & conquer 也不是不行，但是极其麻烦，如图所示：

对于每一个节点，我们需要考虑其左子树的 String, value，还有抹去最后一步运算的 String 与 value .. 对于右子树，我们还需要其抹去第一步运算的 String 与 value 才能正确做 join.

所以说，珍爱生命，有乘法就远离 divide & conquer 吧。

一个思路不错的帖子，这种做法就不用考虑 join了，只要做乘法的时候看它的前一个元素就行；

流程：

• dfs + backtracking 思路

• 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);
            }
        }
    }
}

Basic Calculator

计算器类问题，离不开 Dijkstra 的 Shunting-yard algorithm 和 reverse polish notation.

Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

• 因为有负号，运算顺序不能颠倒；

• 数字可能是多数位的，也可能是0，不能 assume 都是一位数；

• 带括号的处理方式；

复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。

• 建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；

• 如果看到数字，直接添加到 StringBuilder 中；

• 如果看到 "(" ，直接添加到 Stack 上；

• 如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；

• 如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。

• 优先级 ："乘除 = 3"， "加减 = 2”

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();
    }
}

Basic Calculator II

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;
    }
}