为运算表达式设计优先级

题目描述：

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：

输入：expression = “2-1-1”
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2：

输入：expression = “23-45”
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

提示：

1 <= expression.length <= 20
expression 由数字和算符 ‘+’、’-‘ 和 ‘*’ 组成。
输入表达式中的所有整数值在范围 [0, 99]

思路:

时间复杂度：O(n^2),空间复杂度O(2^n)

分治应该是最简单和易于理解的方法了

代码:

func diffWaysToCompute(expression string) (res []int) {
    if isDigit(expression){
        tmp,_ := strconv.Atoi(expression)
        return []int{tmp}
    }
    for index,c := range expression{
        if c == '+' || c == '-' || c == '*'{
            left := diffWaysToCompute(expression[:index])
            right := diffWaysToCompute(expression[index+1:])
            for _,l := range left{
                for _,r := range right{
                    if c == '+'{
                        res = append(res, l+r)
                    }
                    if c== '-'{
                        res = append(res, l-r)
                    }
                    if c == '*'{
                        res = append(res, l*r)
                    }
                }
            }
        }
    }
    return res
}

// 判断是否为全数字
func isDigit(input string) bool {
    _, err := strconv.Atoi(input)
    if err != nil {
        return false
    }
    return true
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.2 MB, 在所有 Go 提交中击败了31.96%的用户