LeetCode 241 Different Ways to Add Parentheses

LeetCode

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.

Example 1:

Input: expression = “2-1-1”
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

Input: expression = “23-45”
Output: [-34,-14,-10,-10,10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

Constraints:

1 <= expression.length <= 20 expression consists of digits and the operator '+', '-', and '*'.
* All the integer values in the input expression are in the range [0, 99].

题目大意：

给定一个字符串含数字和加减乘除，求所有加括号方法得到的结果

Catalan解题思路(推荐)：

求所有结果，用DFS，由于需要左右递归，双边递归，所以用Catalan法模板

解题步骤：

N/A

注意事项：

1. 终止条件返回是一个list
2. Python中用eval来计算字符串运算结果返回值为整数，所以归纳左右递归结果要用str转为字符串

Python代码：

def diffWaysToCompute(self, expression: str) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.diffWaysToCompute(expression[:i])
		right_res = self.diffWaysToCompute(expression[i + 1:])
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

---

记忆性搜索算法II解题思路：

大致同上，只不过加入记忆性搜索算法，但优化不算大

Python代码：

def diffWaysToCompute2(self, expression) -> List[int]:
	return self.dfs(expression, {})

def dfs(self, expression: str, cache) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	if expression in cache:
		return cache[expression]
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.dfs(expression[:i], cache)
		right_res = self.dfs(expression[i + 1:], cache)
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	cache[expression] = res
	return res