different_ways_to_add_parentheses

hitzzc · hitzzc · commit 60cf4ccc9e60 · 2016-10-20T16:25:33.000+08:00
diff --git a/README.md b/README.md
@@ -196,6 +196,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [238. product of array except self](https://github.com/hitzzc/go-leetcode/tree/master/product_of_array_except_self)
 #### [239. Sliding Window Maximum](https://github.com/hitzzc/go-leetcode/tree/master/sliding_window_maximum)
 #### [240. Search a 2D Matrix II](https://github.com/hitzzc/go-leetcode/tree/master/search_a_2D_matrix_II)
+#### [241. Different Ways to Add Parentheses](https://github.com/hitzzc/go-leetcode/tree/master/different_ways_to_add_parentheses)
 
 
 
diff --git a/different_ways_to_add_parentheses/different_ways_to_add_parentheses.go b/different_ways_to_add_parentheses/different_ways_to_add_parentheses.go
@@ -0,0 +1,40 @@
+package different_ways_to_add_parentheses
+
+import (
+	"strconv"
+)
+
+func diffWaysToCompute(input string) []int {
+	return helper(input, map[string][]int{})
+}
+
+func helper(input string, cache map[string][]int) []int {
+	if v, ok := cache[input]; ok {
+		return v
+	}
+	ret := []int{}
+	for i := range input {
+		if input[i] == '+' || input[i] == '-' || input[i] == '*' {
+			left := helper(input[:i], cache)
+			right := helper(input[i+1:], cache)
+			for j := range left {
+				for k := range right {
+					switch input[i] {
+					case '+':
+						ret = append(ret, left[j]+right[k])
+					case '-':
+						ret = append(ret, left[j]-right[k])
+					case '*':
+						ret = append(ret, left[j]*right[k])
+					}
+				}
+			}
+		}
+	}
+	if len(ret) == 0 {
+		num, _ := strconv.Atoi(input)
+		ret = append(ret, num)
+	}
+	cache[input] = ret
+	return ret
+}
