aboutsummaryrefslogtreecommitdiff
path: root/diff_add_parentheses.py
diff options
context:
space:
mode:
Diffstat (limited to 'diff_add_parentheses.py')
-rw-r--r--diff_add_parentheses.py40
1 files changed, 40 insertions, 0 deletions
diff --git a/diff_add_parentheses.py b/diff_add_parentheses.py
new file mode 100644
index 0000000..6adec51
--- /dev/null
+++ b/diff_add_parentheses.py
@@ -0,0 +1,40 @@
+# 241. 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. the test cases are
+generated such that the output values fit in a 32-bit integer and the number
+of different results does not exceed 10^4
+"""
+
+
+class Solution(object):
+ def dfs(self, expression, m):
+ if expression in m:
+ return m[expression]
+ if expression.isdigit():
+ m[expression] = int(expression)
+ return [int(expression)]
+ res = []
+ for i, j in enumerate(expression):
+ if j in "+-*":
+ l = self.diffWaysToCompute(expression[:i])
+ r = self.diffWaysToCompute(expression[i + 1 :])
+ res.extend(eval(str(x) + j + str(y)) for x in l for y in r)
+ m[expression] = res
+ return res
+
+ def diffWaysToCompute(self, expression):
+ """
+ :type expression: str
+ :rtype: List[int]
+ """
+ m = {}
+ return self.dfs(expression, m)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.diffWaysToCompute(expression="2-1-1"))
+ print(obj.diffWaysToCompute(expression="2*3-4*5"))