LeetCode 241 Different Ways to Add Parentheses
概述
https://leetcode.com/problems/different-ways-to-add-parentheses/
分治法
遍历每一个运算符作为最终的运算符，左右两端分治。
（离谱，换了下内层的写法没想到运行时间和内存消耗差别这么大，按理说根本不影响逻辑才对）
class Solution {
public:
vector<string> e;
vector<int> diffWaysToCompute(string expression) {
string t;
for (auto c : expression) {
if (!isdigit(c)) {
e.push_back(t);
e.push_back(string(1, c));
t = "";
} else {
t += c;
}
}
e.push_back(t);
return helper(0, e.size() - 1);
}
vector<int> helper(int l, int r) {
if (l == r) return {stoi(e[l])};
vector<int> ans;
for (int i = l; i <= r; i ++) {
if (e[i] == "*" || e[i] == "+" || e[i] == "-") {
vector<int> ln = helper(l, i-1);
vector<int> rn = helper(i+1, r);
for (auto a : ln) {
for (auto b : rn) {
if (e[i] == "*") {
ans.push_back(a * b);
} else if (e[i] == "+") {
ans.push_back(a + b);
} else {
ans.push_back(a - b);
}
}
}
}
}
return ans;
}
};