LeetCode | 241.为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression ,按不同优先级组合数字和运算符,计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围,不同结果的数量不超过 104 。
示例 1:
输入:expression = "2-1-1"
输出:[0,2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入:expression = "2*3-4*5"
输出:[-34,-14,-10,-10,10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
提示:
- 1 <= expression.length <= 20
- expression 由数字和算符 '+'、'-' 和 '*' 组成。
- 输入表达式中的所有整数值在范围 [0, 99]
思路:
带备忘录的动态规划,用小问题的解去计算大问题。一开始还没想到怎么写,陷入的表达式的分解,一看到表达式是字符串,就去想怎么解析表达式,用什么保存数字,用什么保存操作符了。
其实不需要关心这些,只需要遍历字符串,对每个操作符两边的表达式可能的结果做组合就行。
vector<int> diffWaysToCompute(string expression) {
unordered_map<string, vector<int>> mp;
return helper(mp, expression);
}
vector<int> helper(unordered_map<string, vector<int>> &mp, string str) {
vector<int> result;
for (int i = 0; i < str.size(); ++i) {
char ch = str[i];
if (ch == '+' || ch == '-' || ch == '*') {
vector<int> l, r;
// 计算左边的表达式所有可能的结果
string left = str.substr(0, i);
if (mp.count(left))
l = mp[left];
else
l = helper(mp, left);
// 计算右边的表达式所有可能的结果
string right = str.substr(i + 1, str.size());
if (mp.count(right))
r = mp[right];
else
r = helper(mp, right);
// 左右两边表达式所有的结果进行合并
for (auto & i : l) {
for (auto &j : r) {
if (ch == '+')
result.push_back(i + j);
else if (ch == '-')
result.push_back(i - j);
else
result.push_back(i * j);
}
}
}
}
if (result.size() == 0)
result.push_back(stoi(str));
mp[str] = result;
return result;
}
标签:ch,优先级,241,result,str,expression,LeetCode,表达式,mp
From: https://www.cnblogs.com/AngleLin/p/17361862.html