【leetcode笔记】Python实现 LeetCode 241. Different Ways to Add Parentheses

题目：https://leetcode.com/problems/different-ways-to-add-parentheses/description/

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: “2-1-1”.

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: “23-45”

(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

分析：
递归，笛卡尔积
代码：

class Solution:
  def diffWaysToCompute(self, input):    
    ops = {'+': lambda x, y: x + y,
           '-': lambda x, y: x - y,
           '*': lambda x, y: x * y}
    def ways(s):
      ans = []
      for i in range(len(s)):
        if s[i] in "+-*":          
          ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]
      if not ans: ans.append(int(s))
      return ans
    return ways(input)

代码转自：https://zxi.mytechroad.com/blog/leetcode/leetcode-241-different-ways-to-add-parentheses/