LeetCode 241题的题目是“Different Ways to Add Parentheses”，中文可以翻译为“为表达式添加括号的不同方式”。这道题要求我们给定一个包含数字和运算符的字符串，返回所有可能的加括号方式的结果。

题目描述

给定一个表达式字符串 expression，该字符串只包含数字和算术运算符 +, -, *。你需要找到所有可能的加括号方式，使得该表达式的结果不同，并返回这些结果。

示例

输入: "2-1-1" 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2

输入: "23-45" 输出: [-34, -14, -10, -10, 10] 解释: (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10

解题思路

这道题可以使用分治法和递归的方法来解决。基本思路是将表达式按照运算符进行分割，然后递归地计算左右子表达式的所有可能结果，最后根据当前运算符将左右子表达式的结果进行组合。

具体步骤

1. 递归分割：
   • 遍历表达式中的每一个字符。
   • 如果当前字符是运算符，则将表达式分割为左右两部分，分别递归计算这两部分的所有可能结果。
2. 组合结果：
   • 根据当前运算符，将左右子表达式的结果进行组合，得到当前表达式的所有可能结果。
3. 递归终止条件：
   • 如果当前子表达式不包含任何运算符，即仅为一个数字，则直接返回该数字。

代码实现

以下是使用Python实现的代码：

def diffWaysToCompute(expression: str): def compute(left, right, op): result = [] for l in left: for r in right: if op == '+': result.append(l + r) elif op == '-': result.append(l - r) elif op == '': result.append(l r) return result

if expression.isdigit():
    return [int(expression)]

results = []
for i, char in enumerate(expression):
    if char in "+-*":
        left_results = diffWaysToCompute(expression[:i])
        right_results = diffWaysToCompute(expression[i+1:])
        results.extend(compute(left_results, right_results, char))

return results

print(diffWaysToCompute("2-1-1")) # 输出: [0, 2] print(diffWaysToCompute("23-45")) # 输出: [-34, -14, -10, -10, 10]

解释

1. compute函数：
   • 该函数用于根据运算符 op，将左右子表达式的结果列表 left 和 right 进行组合计算。
2. 主函数diffWaysToCompute：
   • 首先检查当前表达式是否仅为数字，如果是则直接返回该数字。
   • 遍历表达式中的每一个字符，如果遇到运算符，则递归计算左右子表达式的所有可能结果，并使用 compute 函数进行组合。

复杂度分析

• 时间复杂度：由于每个运算符都会将表达式分割为两部分进行递归计算，最坏情况下时间复杂度为 (O(3^n))，其中 (n) 是运算符的数量。
• 空间复杂度：递归调用栈的深度为 (O(n))，此外还需要存储所有可能的结果，空间复杂度也为 (O(3^n))。

通过上述方法，我们可以有效地解决LeetCode 241题，找到所有可能的加括号方式及其结果。