Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - CPP - 241. Different Ways to Add Parentheses

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4682458.html

題目：


解答：

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        auto dfs = [&](this auto&& dfs, string s) -> vector<int> {
            vector<int> ans;

            for (int i = 0; i < s.size(); ++i) {
                char ch = s[i];

                if (ch == '+' || ch == '-' || ch == '*') {
                    vector<int> left = dfs(s.substr(0, i));
                    vector<int> right = dfs(s.substr(i + 1));

                    for (int l : left) {
                        for (int r : right) {
                            if (ch == '+') {
                                ans.push_back(l + r);
                            }
                            else if (ch == '-') {
                                ans.push_back(l - r);
                            }
                            else {
                                ans.push_back(l * r);
                            }
                        }
                    }
                }
            }

            if (ans.empty()) {
                ans.push_back(stoi(s));
            }

            return ans;
        };

        return dfs(expression);
    }
};