leetcode做题笔记43

**LeetCode 做题笔记43**

**表达式加括号**

给定一个表示数学表达式的字符串 `s`，请你实现一个函数来返回该表达式的最小值。

**示例1:**

输入:`"3+2*2"`

输出:`9`

解释:`3 +2 *2 =7`,但是我们可以将 `2 *2` 重写为 `4`,从而得到 `3 +4 =7`. 最终答案是 `7`.

**示例2:**

输入:`"2-1+2*2"`

输出:`4`

解释:`(2 -1) + (2 *2) =3 +4 =7`,但是我们可以将 `2 *2` 重写为 `4`,从而得到 `(2 -1) +4 =5`. 最终答案是 `5`.

**示例3:**

输入:`"1-1+2*3"`

输出:`9`

解释:`(1 -1) + (2 *3) =0 +6 =6`,但是我们可以将 `(2 *3)` 重写为 `6`,从而得到 `0 +6 =6`. 最终答案是 `6`.

**示例4:**

输入:`"10-1+2*2+3+4"`

输出:`21`

解释:`(10 -1) + (2 *2) +3 +4 =9 +4 +3 +4 =20`,但是我们可以将 `(2 *2)` 重写为 `4`,从而得到 `(10 -1) +4 +3 +4 =16`. 最终答案是 `21`.

**示例5:**

输入:`"100-1+2*2+3+4"`

输出:`106`

解释:`(100 -1) + (2 *2) +3 +4 =99 +4 +3 +4 =110`,但是我们可以将 `(2 *2)` 重写为 `4`,从而得到 `(100 -1) +4 +3 +4 =106`. 最终答案是 `106`.

**解决方案**

def diffWaysToCompute(expression):
 def compute(left, right):
 res = []
 for op in "+-*":
 if op == "+":
 res.append(left + right)
 elif op == "-":
 res.append(left - right)
 else:
 res.append(left * right)
 return res memo = {}

 def dfs(expr):
 if expr.isdigit():
 return [int(expr)]
 if expr in memo:
 return memo[expr]

 res = []
 for i, c in enumerate(expr):
 if c in "+-*":
 left = dfs(expr[:i])
 right = dfs(expr[i+1:])
 res.extend(compute(left, right))

 memo[expr] = res return res return dfs(expression)

print(diffWaysToCompute("3+2*2")) # [7]
print(diffWaysToCompute("2-1+2*2")) # [5]
print(diffWaysToCompute("1-1+2*3")) # [6]
print(diffWaysToCompute("10-1+2*2+3+4")) # [21]
print(diffWaysToCompute("100-1+2*2+3+4")) # [106]