題目描述

這是 LeetCode 上的 241. 為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí) 碉渡，難度為 中等帆疟。

Tag : 「DFS」页衙、「爆搜」

給你一個(gè)由數(shù)字和運(yùn)算符組成的字符串 expression疯趟，按不同優(yōu)先級(jí)組合數(shù)字和運(yùn)算符，計(jì)算并返回所有可能組合的結(jié)果认然。你可以 按任意順序 返回答案卦尊。

生成的測(cè)試用例滿足其對(duì)應(yīng)輸出值符合 位整數(shù)范圍，不同結(jié)果的數(shù)量不超過(guò) 报亩。

示例 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 由數(shù)字和算符 '+'浴鸿、'-' 和 '*' 組成。
• 輸入表達(dá)式中的所有整數(shù)值在范圍

DFS

為了方便弦追，我們令 expression 為 s岳链。

數(shù)據(jù)范圍為 ，且要統(tǒng)計(jì)所有的計(jì)算結(jié)果劲件，我們可以運(yùn)用 DFS 爆搜所有方案掸哑。

給定的 s 只有數(shù)字和運(yùn)算符，我們可以根據(jù)運(yùn)算符將式子分為左右兩部分零远，設(shè)計(jì)遞歸函數(shù) List<Integer> dfs(int l, int r)苗分，含義為搜索子串 的所有運(yùn)算結(jié)果。

最終答案為 dfs(0,n-1)牵辣，其中 為入?yún)⒆址拈L(zhǎng)度摔癣，同時(shí)我們有顯而易見的遞歸出口：當(dāng)給定的 不包含任何運(yùn)算符時(shí)，搜索結(jié)果為 所代表的數(shù)字本身。

考慮如何對(duì)任意 進(jìn)行計(jì)算：我們可以通過(guò)枚舉 范圍內(nèi)的所有的運(yùn)算符位置來(lái)進(jìn)行爆搜择浊，假設(shè)當(dāng)前枚舉到的 為運(yùn)算符戴卜，我們可以遞歸運(yùn)算符的左邊 dfs(l,i-1) 拿到左邊所有的結(jié)果，遞歸運(yùn)算符右邊 dfs(i+1,r) 拿到右邊的所有結(jié)果琢岩，結(jié)合「乘法原理」即可知道以當(dāng)前運(yùn)算符 為分割點(diǎn)的表達(dá)式的所有方案投剥。

不難發(fā)現(xiàn)，上述過(guò)程都是由「小表達(dá)式」的結(jié)果推導(dǎo)出「大表達(dá)式」的結(jié)果担孔，因此也可以運(yùn)用「區(qū)間 DP」方式進(jìn)行求解江锨，復(fù)雜度與 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;
    }
}

• 時(shí)間復(fù)雜度：復(fù)雜度與最終結(jié)果數(shù)相關(guān)糕篇，最終結(jié)果數(shù)為「卡特蘭數(shù)」泳桦，復(fù)雜度為
• 空間復(fù)雜度：復(fù)雜度與最終結(jié)果數(shù)相關(guān)，最終結(jié)果數(shù)為「卡特蘭數(shù)」娩缰，復(fù)雜度為

最后

這是我們「刷穿 LeetCode」系列文章的第 No.241 篇灸撰，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目拼坎，部分是有鎖題浮毯，我們將先把所有不帶鎖的題目刷完。

在這個(gè)系列文章里面泰鸡，除了講解解題思路以外债蓝，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板盛龄。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼饰迹，我建立了相關(guān)的倉(cāng)庫(kù)：https://github.com/SharingSource/LogicStack-LeetCode 。

在倉(cāng)庫(kù)地址里余舶，你可以看到系列文章的題解鏈接啊鸭、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解匿值。

更多更全更熱門的「筆試/面試」相關(guān)資料可訪問(wèn)排版精美的 合集新基地 ????

本文由mdnice多平臺(tái)發(fā)布