241. 為運算表達式設計優先級 : DFS 運用題

題目描述

這是 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{
        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      

• 時間複雜度：複雜度與最終結果數相關，最終結果數為「卡特蘭數」，複雜度為
• 空間複雜度：複雜度與最終結果數相關，最終結果數為「卡特蘭數」，複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.241​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。