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
}