241. 为运算表达式设计优先级 : DFS 运用题程序员

题目描述这是 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 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 diffWaysToCompute(String s) { cs = s.toCharArray(); return dfs(0, cs.length - 1); } List dfs(int l, int r) { List ans = new ArrayList<>(); for (int i = l; i <= r; i++) { if (cs[i] >= '0' && cs[i] <= '9') continue; List 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 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地
【241. 为运算表达式设计优先级 : DFS 运用题】本文由mdnice多平台发布