共计 1818 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 241. 为运算表达式设计优先级 ，难度为 中等。
Tag :「DFS」、「爆搜」
给你一个由数字和运算符组成的字符串 expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的后果。你能够 按任意程序 返回答案。
生成的测试用例满足其对应输入值合乎 $32$ 位整数范畴，不同后果的数量不超过 $10^4$。
示例 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]$
DFS
为了不便，咱们令 expression 为 s。
数据范畴为 $20$，且要统计所有的计算结果，咱们能够使用 DFS 爆搜所有计划。
给定的 s 只有数字和运算符，咱们能够依据运算符将式子分为左右两局部，设计递归函数 List<Integer> dfs(int l, int r)，含意为搜寻子串 $s[l…r]$ 的所有运算后果。
最终答案为 dfs(0,n-1)，其中 $n$ 为入参字符串的长度，同时咱们有不言而喻的递归进口：当给定的 $s[l…r]$ 不蕴含任何运算符时，搜寻后果为 $s[l…r]$ 所代表的数字自身。
思考如何对任意 $s[l…r]$ 进行计算：咱们能够通过枚举 $s[l…r]$ 范畴内的所有的运算符地位来进行爆搜，假如以后枚举到的 $s[i]$ 为运算符，咱们能够递归运算符的右边 dfs(l,i-1) 拿到右边所有的后果，递归运算符左边 dfs(i+1,r) 拿到左边的所有后果，联合「乘法原理」即可晓得以以后运算符 $s[i]$ 为宰割点的表达式的所有计划。
不难发现，上述过程都是由「小表达式」的后果推导出「大表达式」的后果，因而也能够使用「区间 DP」形式进行求解，复杂度与 DFS 统一。
代码：
class Solution {char[] cs;
public List<Integer> diffWaysToCompute(String s) {cs = s.toCharArray();
return dfs(0, cs.length - 1);
}
List<Integer> dfs(int l, int r) {List<Integer> ans = new ArrayList<>();
for (int i = l; i <= r; i++) {if (cs[i] >= '0' && cs[i] <= '9') continue;
List<Integer> l1 = dfs(l, i - 1), l2 = dfs(i + 1, r);
for (int a : l1) {for (int b : l2) {
int cur = 0;
if (cs[i] == '+') cur = a + b;
else if (cs[i] == '-') cur = a - b;
else cur = a * b;
ans.add(cur);
}
}
}
if (ans.isEmpty()) {
int cur = 0;
for (int i = l; i <= r; i++) cur = cur * 10 + (cs[i] - '0');
ans.add(cur);
}
return ans;
}
}- 工夫复杂度：复杂度与最终后果数相干，最终后果数为「卡特兰数」，复杂度为 $O(C_{n})$
- 空间复杂度：复杂度与最终后果数相干，最终后果数为「卡特兰数」，复杂度为 $O(C_{n})$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.241 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
