C++ 3ms solution, divide and conquer + memoization


  • 0
    B
    class Solution {
    public:
        vector<int>& diffWaysToCompute(unordered_map<int,vector<int>>& mm,
                                       vector<int>& token, int first, int last) {
            int key = first * ((int)token.size() + 1) + last;
            if (mm.find(key) != mm.end())
                return mm[key];
            
            vector<int> res;
            
            if (first + 1 == last) {
                res.push_back(token[first]);
            } else {
                for (int i = first + 1; i < last; i += 2) {
                    vector<int>& l = diffWaysToCompute(mm, token, first, i);
                    vector<int>& r = diffWaysToCompute(mm, token, i + 1, last);
                    for (auto v1 : l) {
                        for (auto v2 : r) {
                            switch (token[i]) {
                            case '+': res.push_back(v1 + v2); break;
                            case '-': res.push_back(v1 - v2); break;
                            case '*': res.push_back(v1 * v2); break;
                            }
                        }
                    }
                }
            }
            
            return mm[key] = std::move(res);
        }
        
        vector<int> diffWaysToCompute(string input) {
            vector<int> token;
            unordered_map<int,vector<int>> mm;
            
            int v = 0;
            for (auto ch : input) {
                if (isdigit(ch))
                    v = v * 10 + (ch - '0');
                else {
                    token.push_back(v);
                    token.push_back(ch);
                    v = 0;
                }
            }
            token.push_back(v);
    
            vector<int>& res = diffWaysToCompute(mm, token, 0, (int)token.size());
            sort(res.begin(), res.end());
            
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.