Solution to LeetCode 241 Different Ways to Add Parentheses.
LeetCode 241
Different Ways to Add Parentheses (Medium). [link]
Define $DP[i][j]$ as the results of the expression from the ith number to the jth number. The final answer is $DP[0][N-1]$. The subproblems are the operation of $DP[i][k]$ and $DP[k+1][j]$, $i \leq k \leq j-1$.
class Solution(object):
def diffWaysToCompute(self, expression):
"""
:type expression: str
:rtype: List[int]
"""
if expression.isdigit(): # return integer if there is no operator
return [int(expression)]
def operation(c, l, r): # a function to do operations
l = int(l)
r = int(r)
if c == '+':
return l + r
elif c == '-':
return l - r
else:
return l * r
res = []
for i, char in enumerate(expression):
if char in ['+', '-', '*']:
left = self.diffWaysToCompute(expression[:i]) # left
right = self.diffWaysToCompute(expression[i+1:]) # right
for l in left:
for r in right:
res.append(operation(char, l, r))
return res
