java - LeetCode 的时空复杂度是多少 241. 括号的不同添加方式？

Question

我试图了解什么是 leetcode 241 的时间复杂度。添加括号的不同方法。我使用了内存技术。我的 friend 在 Google 编码回合中被问到，他无法给出正确的时间和空间复杂度。我在 Leetcode 中发现了同样的问题。
问题:
给定一串数字和运算符，返回计算所有可能的对数字和运算符进行分组的方法的所有可能结果。有效的运算符是 +、- 和 *。
示例 1:
输入:“2-1-1”
输出:[0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入:“2 * 3 - 4 * 5”
输出:[-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((23)-(45)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
代码:

import java.util.*;

class Solution {
    Map<String, List<Integer>> map = new HashMap<>(); 
    public List<Integer> diffWaysToCompute(String input) {
        if(map.containsKey(input)) {
            return map.get(input);
        }
        
        List<Integer> result = new ArrayList<>();
        int length = input.length();
        
        for(int i = 0; i< length; i++) {
            char character = input.charAt(i);
            if(isOperator(character)) {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i + 1);
                List<Integer> part1Result = diffWaysToCompute(part1);
                List<Integer> part2Result = diffWaysToCompute(part2);
                computeAndStoreResult(input, result, i, part1Result, part2Result);
        
            }
        }
        //store in map...
        map.put(input, result);
        //this is when only one input is present. 
        // input 3 ==> nothing is added in result so add 3 ...
        if(result.size() == 0) {
            result.add(Integer.valueOf(input));
        }
        return result;
    }
    
    private boolean isOperator(char character) {
        return character == '-' || character == '*' || character == '+';
    }
    
    private void computeAndStoreResult(String input, List<Integer> result, int i, List<Integer> part1Result, List<Integer> part2Result) {
        for(Integer p1 : part1Result) {
            for(Integer p2 : part2Result) {
                int c= 0;
                switch (input.charAt(i)) {
                    case '+':
                        c = p1+p2;
                        break;
                    case '-':
                        c = p1-p2;
                        break;
                    case '*':
                        c = p1*p2;
                        break;
                }
                result.add(c);
            }
        }
    }
}

我在很多网站上研究都找不到好的解释
这就是递归树的样子:使用的技术是通过内存进行分而治之。

我找到了一些有用的链接。
https://www.cnblogs.com/yrbbest/p/5006196.html
https://just4once.gitbooks.io/leetcode-notes/content/leetcode/divide-and-conquer/241-different-ways-to-add-parentheses.html

Answer 1

观察

如果表达式由单个数字组成，则有 1放置括号的方法。

如果只有 1表达式中的数学运算符，那么只有 1放置括号以获得相关结果的方法。例如，对于 3 + 4它是 (3 + 4) .

如果有2表达式中的数学运算符，则有 2放置括号的方法。例如，对于 3 + 4 - 2 ，该方法将通过 + 拆分表达式进入 3和 4 - 2 ，然后通过 -进入 3 + 4和 2 .所以，它是 2方法。

如果有3表达式中的数学运算符，那么它是 5结果。例如，1 + 2 - 3 * 4可以拆分为1和 2 - 3 * 4 , 1 + 2和 3 * 4 , 1 + 2 - 3 and 4 . As we've learned from 2) and 3), the number of ways is 2 + 1 + 2 = 5` 种方式。

如果有4表达式中的数学运算符，那么它是 14结果。例如，1 + 2 - 3 * 4 + 5可以拆分为1和 2 - 3 * 4 + 5 , 1 + 2和 3 * 4 + 5 , 1 + 2 - 3和 4 + 5 , 1 + 2 - 3 * 4和 5 .正如我们从 2)、3) 和 4) 中了解到的，方式的数量是 5 + 2 + 2 + 5 = 14方式相应。

如果序列继续，那么它将是 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ... .如您所见，它呈指数增长。
这样的数字序列有一个名字，叫做 Catalan numbers .
算法的应用
正如您可能已经意识到的那样，即使在您获得由第一个数学运算符拆分的左右子表达式的结果后，您的算法也会变得指数化。
所以，如果有 10数学运算符，然后在计算第一个配置的结果(表达式由第一个数学运算符拆分)后，它们的数字将为 4862 .
因此，您的时间复杂度不仅是指数级的，而且空间复杂度也是指数级的，因为您将所有结果保存在一个列表中。