241. 为运算表达式设计优先级
题目描述
输入一个字符串 expression，由非负整数和运算符 +、-、* 组成。
可以给这个表达式随意加括号，从而决定各个运算的先后次序。每一种不同的加括号方式都算出一个值。
返回所有加括号方式得到的值，顺序不限。不同方式算出相同的值时，要重复列出。
测试数据保证所有结果都在 32 位整数范围内，结果个数不超过 10^4。
示例 1
输入：expression = "2-1-1" 输出：[2,0]
解释：(2-(1-1)) = 2，((2-1)-1) = 0。
示例 2
输入：expression = "2*3-4*5" 输出：[-34,-10,-14,-10,10]
解释：五种加括号方式：(2*(3-(4*5))) = -34，((2*(3-4))*5) = -10，((2*3)-(4*5)) = -14，(2*((3-4)*5)) = -10，(((2*3)-4)*5) = 10。
数据范围
1 <= expression.length <= 20expression只含数字和运算符+、-、*。- 表达式中的每个整数都在
[0, 99]之间。 - 整数前面不会带表示正负的
+或-。
解题思路：分治 + 记忆化
分治：任何加括号方案都有“最后一步计算”的那个运算符。枚举每个运算符 c 作为最后一步，递归求出左半边和右半边各自所有可能的值，再两两用 c 组合。纯数字直接返回自身。同一个子串可能被多次求解，用 memo 缓存结果。
为什么正确
go(s) 返回子表达式 s 所有加括号方案的值（可重复），数量等于方案数。
复杂度分析
结果数是卡特兰数，时间和空间与结果数量同阶。
易错点
数字可能是两位数，不能按单个字符切分；结果要保留重复值，不同加括号方式得到相同的值也要各算一个。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
memo = {}
def go(s):
if s in memo:
return memo[s]
if s.isdigit():
return [int(s)]
res = []
for i, c in enumerate(s):
if c in '+-*':
for a in go(s[:i]):
for b in go(s[i + 1:]):
res.append(a + b if c == '+' else a - b if c == '-' else a * b)
memo[s] = res
return res
return go(expression)class Solution {
Map<String, List<Integer>> memo = new HashMap<>();
List<Integer> go(String s) {
if (memo.containsKey(s))
return memo.get(s);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '+' || c == '-' || c == '*') {
for (int a : go(s.substring(0, i)))
for (int b : go(s.substring(i + 1)))
res.add(c == '+' ? a + b : c == '-' ? a - b : a * b);
}
}
if (res.isEmpty())
res.add(Integer.parseInt(s));
memo.put(s, res);
return res;
}
public List<Integer> diffWaysToCompute(String expression) {
return go(expression);
}
}class Solution {
public:
unordered_map<string, vector<int>> memo;
vector<int> go(const string& s) {
if (memo.count(s))
return memo[s];
vector<int> res;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (c == '+' || c == '-' || c == '*') {
for (int a : go(s.substr(0, i)))
for (int b : go(s.substr(i + 1)))
res.push_back(c == '+' ? a + b : c == '-' ? a - b : a * b);
}
}
if (res.empty())
res.push_back(stoi(s));
memo[s] = res;
return res;
}
vector<int> diffWaysToCompute(string expression) {
return go(expression);
}
};func diffWaysToCompute(expression string) []int {
memo := map[string][]int{}
var goFn func(s string) []int
goFn = func(s string) []int {
if r, ok := memo[s]; ok {
return r
}
res := []int{}
for i := 0; i < len(s); i++ {
c := s[i]
if c == '+' || c == '-' || c == '*' {
for _, a := range goFn(s[:i]) {
for _, b := range goFn(s[i+1:]) {
if c == '+' {
res = append(res, a+b)
} else if c == '-' {
res = append(res, a-b)
} else {
res = append(res, a*b)
}
}
}
}
}
if len(res) == 0 {
v, _ := strconv.Atoi(s)
res = append(res, v)
}
memo[s] = res
return res
}
return goFn(expression)
}var diffWaysToCompute = function(expression) {
const memo = new Map();
const go = (s) => {
if (memo.has(s))
return memo.get(s);
const res = [];
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === '+' || c === '-' || c === '*') {
for (const a of go(s.slice(0, i)))
for (const b of go(s.slice(i + 1)))
res.push(c === '+' ? a + b : c === '-' ? a - b : a * b);
}
}
if (res.length === 0)
res.push(Number(s));
memo.set(s, res);
return res;
};
return go(expression);
};function diffWaysToCompute(expression: string): number[] {
const memo = new Map<string, number[]>();
const go = (s: string): number[] => {
if (memo.has(s))
return memo.get(s);
const res: number[] = [];
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === '+' || c === '-' || c === '*') {
for (const a of go(s.slice(0, i)))
for (const b of go(s.slice(i + 1)))
res.push(c === '+' ? a + b : c === '-' ? a - b : a * b);
}
}
if (res.length === 0)
res.push(Number(s));
memo.set(s, res);
return res;
};
return go(expression);
}其他解法
两种方法的状态是同一个：子表达式的所有可能结果。分治自顶向下按运算符切分，区间 DP 自底向上按区间长度填表。结果列表的顺序不同，但多重集一致。
解法 2：区间动态规划 时间 O(2^n)，空间 O(2^n)
先把表达式拆成数字和运算符交替的列表，共 m 个数字。dp[i][j] 表示第 i 到第 j 个数字组成的子表达式所有可能的结果。按区间长度从小到大计算：枚举最后一步计算的运算符位置 k，把 dp[i][k] 和 dp[k+1][j] 中的结果两两组合。答案是 dp[0][m-1]。
不需要递归，状态用数字下标表示，比用子串作记忆化的键更省。结果数量本身是卡特兰数级别，整体复杂度和分治相同。
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
nums, ops = [], []
num = 0
for c in expression:
if c.isdigit():
num = num * 10 + int(c)
else:
nums.append(num)
ops.append(c)
num = 0
nums.append(num)
m = len(nums)
dp = [[[] for _ in range(m)] for _ in range(m)]
for i in range(m):
dp[i][i] = [nums[i]]
for length in range(2, m + 1):
for i in range(m - length + 1):
j = i + length - 1
for k in range(i, j):
op = ops[k]
for a in dp[i][k]:
for b in dp[k + 1][j]:
dp[i][j].append(a + b if op == '+' else a - b if op == '-' else a * b)
return dp[0][m - 1]class Solution {
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> nums = new ArrayList<>();
List<Character> ops = new ArrayList<>();
int num = 0;
for (char c : expression.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else {
nums.add(num);
ops.add(c);
num = 0;
}
}
nums.add(num);
int m = nums.size();
List<Integer>[][] dp = new List[m][m];
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
dp[i][j] = new ArrayList<>();
for (int i = 0; i < m; i++) dp[i][i].add(nums.get(i));
for (int len = 2; len <= m; len++) {
for (int i = 0; i + len - 1 < m; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
char op = ops.get(k);
for (int a : dp[i][k])
for (int b : dp[k + 1][j])
dp[i][j].add(op == '+' ? a + b : op == '-' ? a - b : a * b);
}
}
}
return dp[0][m - 1];
}
}class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
vector<int> nums;
vector<char> ops;
int num = 0;
for (char c : expression) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else {
nums.push_back(num);
ops.push_back(c);
num = 0;
}
}
nums.push_back(num);
int m = nums.size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(m));
for (int i = 0; i < m; i++) dp[i][i] = {nums[i]};
for (int len = 2; len <= m; len++) {
for (int i = 0; i + len - 1 < m; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
char op = ops[k];
for (int a : dp[i][k])
for (int b : dp[k + 1][j])
dp[i][j].push_back(op == '+' ? a + b : op == '-' ? a - b : a * b);
}
}
}
return dp[0][m - 1];
}
};func diffWaysToCompute(expression string) []int {
nums, ops := []int{}, []byte{}
num := 0
for i := 0; i < len(expression); i++ {
c := expression[i]
if c >= '0' && c <= '9' {
num = num*10 + int(c-'0')
} else {
nums = append(nums, num)
ops = append(ops, c)
num = 0
}
}
nums = append(nums, num)
m := len(nums)
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, m)
dp[i][i] = []int{nums[i]}
}
for length := 2; length <= m; length++ {
for i := 0; i+length-1 < m; i++ {
j := i + length - 1
for k := i; k < j; k++ {
op := ops[k]
for _, a := range dp[i][k] {
for _, b := range dp[k+1][j] {
switch op {
case '+':
dp[i][j] = append(dp[i][j], a+b)
case '-':
dp[i][j] = append(dp[i][j], a-b)
default:
dp[i][j] = append(dp[i][j], a*b)
}
}
}
}
}
}
return dp[0][m-1]
}var diffWaysToCompute = function(expression) {
const nums = [], ops = [];
let num = 0;
for (const c of expression) {
if (c >= '0' && c <= '9') {
num = num * 10 + Number(c);
} else {
nums.push(num);
ops.push(c);
num = 0;
}
}
nums.push(num);
const m = nums.length;
const dp = Array.from({ length: m }, () => Array.from({ length: m }, () => []));
for (let i = 0; i < m; i++) dp[i][i] = [nums[i]];
for (let len = 2; len <= m; len++) {
for (let i = 0; i + len - 1 < m; i++) {
const j = i + len - 1;
for (let k = i; k < j; k++) {
const op = ops[k];
for (const a of dp[i][k])
for (const b of dp[k + 1][j])
dp[i][j].push(op === '+' ? a + b : op === '-' ? a - b : a * b);
}
}
}
return dp[0][m - 1];
};function diffWaysToCompute(expression: string): number[] {
const nums: number[] = [], ops: string[] = [];
let num = 0;
for (const c of expression) {
if (c >= '0' && c <= '9') {
num = num * 10 + Number(c);
} else {
nums.push(num);
ops.push(c);
num = 0;
}
}
nums.push(num);
const m = nums.length;
const dp: number[][][] = Array.from({ length: m }, () => Array.from({ length: m }, () => []));
for (let i = 0; i < m; i++) dp[i][i] = [nums[i]];
for (let len = 2; len <= m; len++) {
for (let i = 0; i + len - 1 < m; i++) {
const j = i + len - 1;
for (let k = i; k < j; k++) {
const op = ops[k];
for (const a of dp[i][k])
for (const b of dp[k + 1][j])
dp[i][j].push(op === '+' ? a + b : op === '-' ? a - b : a * b);
}
}
}
return dp[0][m - 1];
}