241. Different Ways to Add Parentheses
给一个字串expression是由数字和运算符号组成的运算式
请回传这个运算是所有可能的结果
运算符号只会有'+'、'-'、'*'
思路:
一开始想太复杂了
其实只要用递回去解就好
当你遇到运算符号值就把符号左右两边的字串丢到递回函式中
递回函式会回传整数矩阵
接着把两个回传的整数矩阵进行该符号运算得到所有结果
就可以得到答案了
golang code :
func diffWaysToCompute(expression string) []int {
n := len(expression)
res := []int{}
single_num := true
for i := 0; i < n; i++ {
switch expression[i] {
case '-':
single_num = false
tmp1 := diffWaysToCompute(expression[:i])
tmp2 := diffWaysToCompute(expression[i+1:])
for _, num1 := range tmp1 {
for _, num2 := range tmp2 {
res = append(res, num1-num2)
}
}
case '+':
single_num = false
tmp1 := diffWaysToCompute(expression[:i])
tmp2 := diffWaysToCompute(expression[i+1:])
for _, num1 := range tmp1 {
for _, num2 := range tmp2 {
res = append(res, num1+num2)
}
}
case '*':
single_num = false
tmp1 := diffWaysToCompute(expression[:i])
tmp2 := diffWaysToCompute(expression[i+1:])
for _, num1 := range tmp1 {
for _, num2 := range tmp2 {
res = append(res, num1*num2)
}
}
}
}
if single_num {
num, _ := strconv.Atoi(expression)
return []int{num}
}
return res
}