0241. Different Ways to Add Parentheses¶
题目信息¶
- 题号:
0241
- 难度:
Medium
- 主题:
字符串、分治、记忆化、表达式
- 原题:
- 重点:
枚举所有二元结合方式、运算符只有加减乘、相同结果可以重复、返回顺序不限
题目重述¶
给定一个由非负十进制整数以及 +、-、* 三种二元运算符组成的表达式字符串 expression。通过改变运算的括号分组方式,枚举所有可能的计算结果并返回这些整数。
字符串长度位于 [1, 20],表达式中的整数及所有中间结果、最终结果都适合 32 位有符号整数。不同括号方式即使得到相同数值,也要在结果中保留对应的重复项;返回结果的排列顺序不作要求。题目不是要求生成带括号字符串,而是返回每种合法分组对应的数值。
自建示例¶
减法结合方向不同:
输入:expression = "3-1-2"
输出:[0, 4]
解释:(3-1)-2=0,而 3-(1-2)=4;返回 [4,0] 也同样合法。
不同分组得到重复结果:
输入:expression = "2*2*2"
输出:[8, 8]
解释:(2*2)*2 和 2*(2*2) 是两种不同分组,虽然结果都为 8,两个结果仍需保留。
按最后一个运算符分治¶
任意一种完整加括号方式,都有一个最后执行的二元运算符。若它位于第 mid 个运算符,
左边表达式和右边表达式必须各自独立完成一种合法加括号方式,然后用该运算符组合两侧结果。
因此定义 solve(l,r) 为第 l 到第 r 个数字之间所有可能结果:
for mid in [l, r):
left_results = solve(l, mid)
right_results = solve(mid+1, r)
对每个 left、right 应用 ops[mid]
区间只有一个数字时,唯一结果就是该数字。相同区间会被许多更大区间重复请求,使用区间端点记忆化, 但组合结果本身仍按产生次数加入,不能用集合去重。
正确性说明¶
取任意一种加括号方式,其最外层最后运算符唯一地把表达式分成左右两个连续区间;递归会枚举这个 mid,
并由归纳假设取得左右方式。反过来,任取递归得到的左右结果和一个分割运算符,把两侧加括号后就是合法完整分组。
所以分治既不遗漏也不产生非法方式。不同分组即使数值相同,也在左右结果的笛卡尔积中分别保留。
C++ 实现¶
class Solution {
std::vector<int> numbers;
std::vector<char> operators;
std::map<std::pair<int, int>, std::vector<int>> memo;
std::vector<int> solve(int left, int right) {
const auto key = std::make_pair(left, right);
auto cached = memo.find(key);
if (cached != memo.end()) return cached->second;
if (left == right) {
return memo[key] = {numbers[left]};
}
std::vector<int> result;
for (int mid = left; mid < right; ++mid) {
const std::vector<int> left_results = solve(left, mid);
const std::vector<int> right_results = solve(mid + 1, right);
for (int a : left_results) {
for (int b : right_results) {
if (operators[mid] == '+') result.push_back(a + b);
else if (operators[mid] == '-') result.push_back(a - b);
else result.push_back(a * b);
}
}
}
return memo[key] = result;
}
public:
std::vector<int> diffWaysToCompute(const std::string& expression) {
numbers.clear();
operators.clear();
memo.clear();
int number = 0;
bool reading_number = false;
for (char ch : expression) {
if (ch >= '0' && ch <= '9') {
number = number * 10 + (ch - '0');
reading_number = true;
} else {
numbers.push_back(number);
number = 0;
reading_number = false;
operators.push_back(ch);
}
}
if (reading_number || numbers.empty()) numbers.push_back(number);
return solve(0, static_cast<int>(numbers.size()) - 1);
}
};
代码分析¶
表达式只有非负整数和二元运算符,解析时用连续数字构造多位数。设数字个数为 p,递归深度为 O(p);
记忆化避免重复计算相同区间,但结果列表可能按 Catalan 数量增长,时间和空间必须包含这些输出结果的规模,
不能简单声称为多项式。额外的区间状态数为 O(p^2),返回顺序不影响正确性。