题目描述

这是 LeetCode 上的 241. 为运算表达式设计优先级 ，难度为 中等。

Tag : 「DFS」、「爆搜」

给你一个由数字和运算符组成的字符串?expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 位整数范围，不同结果的数量不超过 。

示例 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

提示：

• expression 由数字和算符 '+'、 '-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围

DFS

为了方便，我们令 expression 为 s。

数据范围为 ，且要统计所有的计算结果，我们可以运用 DFS 爆搜所有方案。

给定的 s 只有数字和运算符，我们可以根据运算符将式子分为左右两部分，设计递归函数 List<Integer> dfs(int l, int r)，含义为搜索子串 的所有运算结果。

最终答案为 dfs(0,n-1)，其中 为入参字符串的长度，同时我们有显而易见的递归出口：当给定的 不包含任何运算符时，搜索结果为 所代表的数字本身。

考虑如何对任意 进行计算：我们可以通过枚举 范围内的所有的运算符位置来进行爆搜，假设当前枚举到的 为运算符，我们可以递归运算符的左边 dfs(l,i-1) 拿到左边所有的结果，递归运算符右边 dfs(i+1,r) 拿到右边的所有结果，结合「乘法原理」即可知道以当前运算符 为分割点的表达式的所有方案。

不难发现，上述过程都是由「小表达式」的结果推导出「大表达式」的结果，因此也可以运用「区间 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;
????}
}

• 时间复杂度：复杂度与最终结果数相关，最终结果数为「卡特兰数」，复杂度为
• 空间复杂度：复杂度与最终结果数相关，最终结果数为「卡特兰数」，复杂度为

最后

这是我们「刷穿 LeetCode」系列文章的第 No.241 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉