Leetcode练习(Python)：分治算法类：第241题：为运算表达式设计优先级：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
题目：
为运算表达式设计优先级：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
思路：
分治算法的核心思想是能将一个复杂的题目拆分为若干简单的小题目，并且通过递归的方式来实现。
在本题中，这个大问题可以拆分成只关于两个数的减价和乘法的运算，通过控制变量，来模拟实现括号存在的样子。
程序：
from functools import lru_cache
class Solution:
def diffWaysToCompute(self, input: str) -> List[int]:
if not input:
return []
result = []
if input.isdigit():
return [int(input)]
length = len(input)
for index2 in range(length):
if input[index2] in "+-*":
leftPart = self.diffWaysToCompute(input[: index2])
rightPart = self.diffWaysToCompute(input[index2 + 1 :])
for index3 in leftPart:
for index4 in rightPart:
if input[index2] == "+":
result.append(index3 + index4)
elif input[index2] == "-":
result.append(index3 - index4)
else:
result.append(index3 * index4)
return result