C++ divide-and-conquer solution (69 ms)


  • 0
    D

    I took a divide-and-conquer approach to this problem, which is in some ways simpler than typical DFS solutions. The key to making this method fast is to keep track of a set of desired target values at each point (at least in addOperatorsHelper(), where it's critical for reducing the search space). It's reasonably fast but not as fast as the fastest DFS solutions, largely due to the overhead of managing large collections of candidate strings.

    class Solution {
        int toInt(const string& num, int i, int len) {
            if (len < 1 || len > 10) return -1;
            if (len > 1 && num[i] == '0') return -1;
            int n = 0;
            for (int j=i; j < i + len; j++) {
                int val = num[j] - '0';
                if (n > (numeric_limits<int>::max() - val)/10) return -1;
                n = (n * 10) + val;
            }
            return n;
        }
        
        unordered_map<int, vector<string>> multiplyHelper(const string& num, int i, int len) {
            unordered_map<int, vector<string>> result;
            int n = toInt(num, i, len); // single value (no multiply)
            if (n >= 0) {
                result[n].push_back(num.substr(i, len));
            }
            if (len >= 2) {
                for (int j = 1; j <= 10 && j < len; j++) {
                    int n = toInt(num, i, j);
                    if (n < 0) continue;
                    unordered_map<int, vector<string>> right = multiplyHelper(num, i + j, len - j);
                    for (auto pair : right) {
                        if (n == 0 || pair.first <= numeric_limits<int>::max()/n) {
                            for (string s : pair.second) {
                                result[n * pair.first].push_back(num.substr(i, j) + "*" + s);
                            }
                        }
                    }
                }
            }
            return result;
        }
        
        unordered_map<int, vector<string>> addOperatorsHelper(const string& num, int i, int len, const set<int>& target) {
            unordered_map<int, vector<string>> result = multiplyHelper(num, i, len); // No add/subtract
            if (len >= 2) {
                for (int j = 1; j < len; j++) {
                    unordered_map<int, vector<string>> right = multiplyHelper(num, i + j, len - j);
                    set<int> targetLeft;
                    for (auto pairRight : right) {
                        int right = pairRight.first;
                        for (int targ : target) {
                            if (targ >= numeric_limits<int>::min() + right) {
                                targetLeft.insert(targ - right);
                            }
                            if (targ <= numeric_limits<int>::max() - right) {
                                targetLeft.insert(targ + right);
                            }
                        }
                    }
                    
                    unordered_map<int, vector<string>> left = addOperatorsHelper(num, i, j, targetLeft);
                    for (auto pairLeft : left) {
                        for (auto pairRight : right) {
                            if (pairLeft.first <= numeric_limits<int>::max() - pairRight.first) {
                                if (target.find(pairLeft.first + pairRight.first) != target.end()) {
                                    for (string sleft : pairLeft.second) {
                                        for (string sright : pairRight.second) {
                                            result[pairLeft.first + pairRight.first].push_back(sleft + "+" + sright);
                                        }
                                    }
                                }
                            }
                            if (pairLeft.first >= numeric_limits<int>::min() + pairRight.first) {
                                if (target.find(pairLeft.first - pairRight.first) != target.end()) {
                                    for (string sleft : pairLeft.second) {
                                        for (string sright : pairRight.second) {
                                            result[pairLeft.first - pairRight.first].push_back(sleft + "-" + sright);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return result;
        }
        
    public:
        vector<string> addOperators(string num, int target) {
            set<int> targetSet;
            targetSet.insert(target);
            unordered_map<int, vector<string>> result = addOperatorsHelper(num, 0, num.length(), targetSet);
            return result[target];
        }
    };

Log in to reply
 

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