【leetcode笔记】Python实现LeetCode241.DifferentWaystoAddParentheses

题目：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/