难度: Medium
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
示例 1：
输入：expression = "2-1-1" 输出：[0,2] 解释： ((2-1)-1) = 0 (2-(1-1)) = 2
示例 2：
输入：expression = "2*3-4*5" 输出：[-34,-14,-10,-10,10] 解释： (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10
提示：
1 <= expression.length <= 20expression 由数字和算符 '+'、'-' 和 '*' 组成。[0, 99] 运行时间: 23 ms
内存: 16.1 MB
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
memory = dict()
def dc(s):
if s in memory:
return memory[s]
elif '+' not in s and '-' not in s and '*' not in s:
return [int(s)]
ans = []
for i in range(len(s)):
if s[i] in '+-*':
left = dc(s[:i])
right = dc(s[i + 1:])
for a in left:
for b in right:
if s[i] == '+':
ans.append(a + b)
elif s[i] == '-':
ans.append(a - b)
else:
ans.append(a * b)
memory[s] = ans
return ans
return dc(expression)
这个题解使用分治算法和记忆化搜索来解决问题。对于给定的表达式，如果它不包含任何运算符，直接将其转换为整数并返回。否则，遍历表达式的每个字符，如果遇到运算符，就将表达式分成左右两部分，递归计算左右两部分的所有可能结果，然后根据运算符对左右两部分的结果进行交叉运算，将所有可能的结果加入答案数组。为了避免重复计算，使用一个字典 memory 来存储已经计算过的子表达式及其结果，这样可以大大减少递归次数，提高效率。
时间复杂度: O(n * 4^n)
空间复杂度: O(n * 2^n)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
memory = dict()
def dc(s):
if s in memory:
return memory[s]
elif '+' not in s and '-' not in s and '*' not in s:
# 如果表达式不包含任何运算符，直接将其转换为整数并返回
return [int(s)]
ans = []
for i in range(len(s)):
if s[i] in '+-*':
left = dc(s[:i]) # 递归计算左半部分的所有可能结果
right = dc(s[i + 1:]) # 递归计算右半部分的所有可能结果
for a in left:
for b in right:
if s[i] == '+':
ans.append(a + b)
elif s[i] == '-':
ans.append(a - b)
else:
ans.append(a * b)
memory[s] = ans # 记忆化搜索，存储已计算过的子表达式及其结果
return ans
return dc(expression)
在题解中，为了正确处理多位数，算法在遇到运算符时将表达式分成左右两部分。当遍历到表达式中的运算符时，会基于运算符的位置将表达式分割为两部分，然后递归地对这两部分进行处理。如果表达式片段不包含任何运算符，表明这是一个完整的数字，无论它是单位数还是多位数，直接将这个字符串转换为整数。这种方法通过递归确保了即使在运算符之间的数是多位数时也能被正确解析和计算。
在记忆化搜索中使用字符串作为字典的键，主要是因为字符串在这种场景下提供了一个直观且易于实现的方式来唯一标识每一个子表达式。字符串能够精确地保持表达式的结构和内容，使得每次递归调用都能快速检查是否已经计算过相同的表达式。使用其他数据结构如数组或编码形式可能会涉及到额外的转换过程，这不仅增加了实现的复杂度，还可能影响查找效率。字符串的哈希查找效率高，易于在字典中进行存储和检索。
记忆化搜索通过存储已经计算过的表达式和它们的结果来减少重复计算，从而提高算法的效率。然而，这种做法确实会增加内存使用量，因为每个不同的子表达式及其结果都会被存储在内存中。在处理较大或复杂的表达式时，内存字典的大小可能会显著增长，潜在地导致较高的内存消耗。如果内存资源有限，存储大量的结果可能会导致内存溢出或性能下降。在实际应用中，需要根据可用资源和表达式的复杂度来权衡记忆化的使用。
在递归分治算法中，整数溢出是一个需要关注的问题，尤其是在处理包含大数运算的表达式时。一种常见的解决策略是使用编程语言提供的大数支持库（如 Python 中的 int 类型自动处理大数问题）。对于不支持大数的语言，可以采用特定的数据结构或库来处理大数运算，以避免溢出。此外，递归函数在进行运算前也可以进行溢出检测，如检查操作数是否超过了数据类型的安全范围，并相应地调整或报错。