[Leetcode] 241. Different Ways to Add Parentheses

 

这一题，并没有太多取巧可言，就是类似backtrack的递归。只是这个和backtrack不太一样，一般的递归不是自上而下就是自下而上的。自上而下的意思就是每一层记录当时的计算结果，然后传递至下一层，直到传递至最后一层base case的时候得到最终结果。自下而上的意思就是，我们不停往下传递中间的计算步骤，然后先往下一个递归层拿一个返回值再做当前层的计算再往上返回，最终结果是在递归的第一层得到的。

这一题的递归分层有一种divide and conquer的感觉。每个计算符相当于一个分割点，将字符串分成左右两边。每一个递归层是一个根据计算符号分割开的子字符串，递归层的base case是当前子字符串是一个数字。用2 * 3 - 4 * 5来说明。
1. 遇到第一个*号的时候，我们可以将该字符串分成两份， 2 和 3 - 4 * 5其中2已经是一个数字了，所以直接返回，3 - 4 * 5里，第二层递归可以按减号分割，然后变成3和4 * 5。因为3是数字，所以直接返回，而4 * 5，我们还是以* 为分界线，分成4 和 5两端，然后两者都是数字，我们就开始实际上的第一个计算，4 * 5 = 20。 然后把 20这个结果返回上一递归层，3 - 20 = -17。 然后在返回上一递归层， 2 * -17 = -34。当然，每一个递归层返回的是一个解集，而不是单独的一个结果，譬如在3 - 4 * 5里，你从减号分是一个结果，从乘号先分将会是另一个结果。所以我们返回的是所有的结果的一个List。这样在最开始的递归层我们就可以直接返回结果就可以了，也不需要另外一个helper function去返回结果。

根据上述算法，给出代码如下：

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new LinkedList<>();
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int leftInt : left) {
                    for (int rightInt : right) {
                        switch(c) {
                            case '+':
                                result.add(leftInt + rightInt);
                                break;
                            case '-':
                                result.add(leftInt - rightInt);
                                break;
                            case '*':
                                result.add(leftInt * rightInt);
                                break;
                            default:
                                break;
                        }
                    }
                }
            }
        }
        
        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }
        
        return result;
    }

需要注意的一点是，正常来说我们需要检查input是否是整型数，是的话就是base case。但这里我们用了一个很巧妙的办法，如果result list是空的话就表示没有经过任何符号，这也就表示当前的string是整型数。这会帮助我们省下一大截用来分析字符串的时间。其实在这之上，我们还可以做一个简单的优化去避免重复计算，就是利用一个Map<String, List<Integer>>去存计算过的子字符串，这样就可以避免反复计算。属于dp的最基本应用方式。

    public List<Integer> diffWaysToCompute(String input) {
        return diffWaysToCompute(input, new HashMap<>());
    }

    public List<Integer> diffWaysToCompute(String input, Map<String, List<Integer>> cache) {
        if (cache.containsKey(input)) return cache.get(input);

        List<Integer> result = new LinkedList<>();
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int leftInt : left) {
                    for (int rightInt : right) {
                        switch(c) {
                            case '+':
                                result.add(leftInt + rightInt);
                                break;
                            case '-':
                                result.add(leftInt - rightInt);
                                break;
                            case '*':
                                result.add(leftInt * rightInt);
                                break;
                            default:
                                break;
                        }
                    }
                }
            }
        }
        
        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }
        
        cache.put(input, result);
        return result;
    }