Leetcode 282 Solution

This article provides solution to leetcode question 282 (expression-add-operators)
Categories:
Tags:
Access this page by simply typing in "lcs 282" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/expression-add-operators

Solution

class Solution {
    vector<string> res;



public:
    void addOperators(const string& num, int i, int64_t diff, int64_t target, int64_t curr, string curr_exp) {
        if (i == num.size())
        {
            if (curr == target)
                res.push_back(curr_exp);
            return;
        }



        for (int j = i; j < num.size(); j++)
        {
            string var = num.substr(i, j - i + 1);
            int64_t ivar = atoll(var.c_str());



            if (to_string(ivar) != var)
                continue;



            if (i == 0)
            {
                addOperators(num, j + 1, ivar, target, ivar, var);
            }
            else
            {
                addOperators(num, j + 1, ivar, target, curr + ivar, curr_exp + "+" + var);
                addOperators(num, j + 1, -ivar, target, curr - ivar, curr_exp + "-" + var);
                addOperators(num, j + 1, ivar * diff, target, curr - diff + diff * ivar, curr_exp + "*" + var);
            }
        }
    }



    vector<string> addOperators(string num, int target) {
        addOperators(num, 0, 0, target, 0, "");
        return res;
    }
};