问题描述
给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:
1 | 输入: "2-1-1" |
示例 2:
1 | 输入: "2*3-4*5" |
分治
分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 首先按操作符循环,即确定分治的出发点。然后分别计算操作符左边结果和操作符右边结果。
1 | class Solution { |
明白一个函数的作用并相信它能完成这个任务,千万不要试图跳进细节
如果在使用分治思想递归过程觉得大问题和子问题函数的返回值不同,说明这个问题分解没想清楚,否则必然是相同的问题,相同的返回值类型。
带备忘录的分治
1 | class Solution { |