原文链接: https://leetcode-cn.com/problems/different-ways-to-add-parentheses

英文原文

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

 

Example 1:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

 

Constraints:

• 1 <= expression.length <= 20
• expression consists of digits and the operator '+', '-', and '*'.
• All the integer values in the input expression are in the range [0, 99].

中文题目

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 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 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

通过代码

高赞题解

题目描述（中等难度）

给一个表达式加括号，得到所有不同情况的解。

解法一 递归

一看到题就觉得有点复杂，可以考虑一下递归的方式，去寻找子问题和原问题解的关系。

可以通过运算符把整个式子分成两部分，两部分再利用递归解决。

以 2 * 3 - 4 * 5 为例。

2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 * 3 和 4 * 5 两部分，中间是 - 号相连。

2 * 3 - 4 和 5 两部分，中间是 * 号相连。

有了两部分的结果，然后再通过中间的符号两两计算加入到最终的结果中即可。

比如第一种情况，2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 的解就是 [2]，3 - 4 * 5 的解就是 [-5, -17]。

把两部分解通过 * 号计算，最终结果就是 [-10, -34]。

另外两种情况也类似。

然后还需要递归出口。

如果给定的字符串只有数字，没有运算符，那结果就是给定的字符串转为数字。

比如上边的第一种情况，2 的解就是 [2]。

public List<Integer> diffWaysToCompute(String input) {

    if (input.length() == 0) {

        return new ArrayList<>();

    }

    List<Integer> result = new ArrayList<>();

    int num = 0;

    //考虑是全数字的情况

    int index = 0;

    while (index < input.length() && !isOperation(input.charAt(index))) {

        num = num * 10 + input.charAt(index) - '0';

        index++;

    }

    //将全数字的情况直接返回

    if (index == input.length()) {

        result.add(num);

        return result;

    }

    

    for (int i = 0; i < input.length(); i++) {

        //通过运算符将字符串分成两部分

        if (isOperation(input.charAt(i))) {

            List<Integer> result1 = diffWaysToCompute(input.substring(0, i));

            List<Integer> result2 = diffWaysToCompute(input.substring(i + 1));

            //将两个结果依次运算

            for (int j = 0; j < result1.size(); j++) {

                for (int k = 0; k < result2.size(); k++) {

                    char op = input.charAt(i);

                    result.add(caculate(result1.get(j), op, result2.get(k)));

                }

            }

        }

    }

    return result;

}



private int caculate(int num1, char c, int num2) {

    switch (c) {

        case '+':

            return num1 + num2;

        case '-':

            return num1 - num2;

        case '*':

            return num1 * num2;

    }

    return -1;

}



private boolean isOperation(char c) {

    return c == '+' || c == '-' || c == '*';

}

由于递归是两个分支，所以会有一些的解进行了重复计算，我们可以通过 memoization 技术，前边很多题都用过了，一种空间换时间的方法。

将递归过程中的解保存起来，如果第二次递归过来，直接返回结果即可，无需重复递归。

将解通过 map 存储，其中，key 存储函数入口参数的字符串，value 存储当前全部解的一个 List 。

//添加一个 map

HashMap<String,List<Integer>> map = new HashMap<>();

public List<Integer> diffWaysToCompute(String input) {

    if (input.length() == 0) {

        return new ArrayList<>();

    }

    //如果已经有当前解了，直接返回

    if(map.containsKey(input)){

        return map.get(input);

    }

    List<Integer> result = new ArrayList<>();

    int num = 0;

    int index = 0;

    while (index < input.length() && !isOperation(input.charAt(index))) {

        num = num * 10 + input.charAt(index) - '0';

        index++;

    }

    if (index == input.length()) {

        result.add(num);

        //存到 map

        map.put(input, result);

        return result;

    }

    for (int i = 0; i < input.length(); i++) {

        if (isOperation(input.charAt(i))) {

            List<Integer> result1 = diffWaysToCompute(input.substring(0, i));

            List<Integer> result2 = diffWaysToCompute(input.substring(i + 1));

            for (int j = 0; j < result1.size(); j++) {

                for (int k = 0; k < result2.size(); k++) {

                    char op = input.charAt(i);

                    result.add(caculate(result1.get(j), op, result2.get(k)));

                }

            }

        }

    }

     //存到 map

    map.put(input, result);

    return result;

}



private int caculate(int num1, char c, int num2) {

    switch (c) {

        case '+':

            return num1 + num2;

        case '-':

            return num1 - num2;

        case '*':

            return num1 * num2;

    }

    return -1;

}



private boolean isOperation(char c) {

    return c == '+' || c == '-' || c == '*';

}

解法二 动态规划

按理说写完递归、 写完 memoization ，接下来动态规划也能顺理成章的写出来了，比如经典的 爬楼梯 问题。但这个如果什么都不处理，dp 数组的含义比较难定义，分享一下 这里 的处理吧。

最巧妙的地方就是做一个预处理，把每个数字提前转为 int 然后存起来，同时把运算符也都存起来。

这样的话我们就有了两个 list，一个保存了所有数字，一个保存了所有运算符。

2 * 3 - 4 * 5

存起来的数字是 numList = [2 3 4 5]，

存起来的运算符是 opList = [*, -, *]。

dp[i][j] 也比较好定义了，含义是第 i 到第 j 个数字（从 0 开始计数）范围内的表达式的所有解。

举个例子，2 * 3 - 4 * 5 

dp[1][3] 就代表第一个数字 3 到第三个数字 5 范围内的表达式 3 - 4 * 5 的所有解。

初始条件的话，也很简单了，就是范围内只有一个数字。

2 * 3 - 4 * 5 

dp[0][0] = [2]，dp[1][1] = [3]，dp[2][2] = [4]，dp[3][3] = [5]。

有了一个数字的所有解，然后两个数字的所有解就可以求出来。

有了两个数字的所有解，然后三个数字的所有解就和解法一求法一样。

把三个数字分成两部分，将两部分的解两两组合起来即可。

两部分之间的运算符的话，因为表达式是一个数字一个运算符，所以运算符的下标就是左部分最后一个数字的下标。

看下边的例子。

2 * 3 - 4 * 5

存起来的数字是 numList = [2 3 4 5]，

存起来的运算符是 opList = [*, -, *]。



假设我们求 dp[1][3]

也就是计算 3 - 4 * 5 的解

分成 3 和 4 * 5 两部分，3 对应的下标是 1 ，对应的运算符就是 opList[1] = '-' 。

也就是计算 3 - 20 = -17

    

分成 3 - 4 和 5 两部分，4 的下标是 2 ，对应的运算符就是 opList[2] = '*'。

也就是计算 -1 * 5 = -5

    

所以 dp[1][3] = [-17 -5]

四个、五个… 都可以分成两部分，然后通过之前的解求出来。

直到包含了所有数字的解求出来，假设数字总个数是 n，dp[0][n-1] 就是最后返回的了。

public List<Integer> diffWaysToCompute(String input) {

    List<Integer> numList = new ArrayList<>();

    List<Character> opList = new ArrayList<>();

    char[] array = input.toCharArray();

    int num = 0;

    for (int i = 0; i < array.length; i++) {

        if (isOperation(array[i])) {

            numList.add(num);

            num = 0;

            opList.add(array[i]);

            continue;

        }

        num = num * 10 + array[i] - '0';

    }

    numList.add(num);

    int N = numList.size(); // 数字的个数



    // 一个数字

    ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];

    for (int i = 0; i < N; i++) {

        ArrayList<Integer> result = new ArrayList<>();

        result.add(numList.get(i));

        dp[i][i] = result;

    }

    // 2 个数字到 N 个数字

    for (int n = 2; n <= N; n++) {

        // 开始下标

        for (int i = 0; i < N; i++) {

            // 结束下标

            int j = i + n - 1;

            if (j >= N) {

                break;

            }

            ArrayList<Integer> result = new ArrayList<>();

            // 分成 i ~ s 和 s+1 ~ j 两部分

            for (int s = i; s < j; s++) {

                ArrayList<Integer> result1 = dp[i][s];

                ArrayList<Integer> result2 = dp[s + 1][j];

                for (int x = 0; x < result1.size(); x++) {

                    for (int y = 0; y < result2.size(); y++) {

                        // 第 s 个数字下标对应是第 s 个运算符

                        char op = opList.get(s);

                        result.add(caculate(result1.get(x), op, result2.get(y)));

                    }

                }

            }

            dp[i][j] = result;



        }

    }

    return dp[0][N-1];

}



private int caculate(int num1, char c, int num2) {

    switch (c) {

        case '+':

            return num1 + num2;

        case '-':

            return num1 - num2;

        case '*':

            return num1 * num2;

    }

    return -1;

}



private boolean isOperation(char c) {

    return c == '+' || c == '-' || c == '*';

}

总

解法一的话是比较直觉的方法，用递归可以将问题简化。

解法二的话，关键就在于字符串的预处理，将数字和运算符分别存起来，很巧妙。然后就能很明确的定义出 dp 的含义，代码就比较容易写出来了。

之前自己在博客总结的，更多题解可以在原地址 https://leetcode.wang。

统计信息

通过次数	提交次数	AC比率
34180	46445	73.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
不同的二叉搜索树 II	中等
基本计算器	困难
给表达式添加运算符	困难