Last updated on July 20th, 2024 at 04:09 am

Here, We see Expression Add Operators LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Divide and Conquer

Companies

Facebook, Google

Level of Question

Hard

Expression Add Operators LeetCode Solution

Problem Statement

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:
Input: num = “123”, target = 6
Output: [“1*2*3″,”1+2+3”]
Explanation: Both “1*2*3” and “1+2+3” evaluate to 6.

Example 2:
Input: num = “232”, target = 8
Output: [“2*3+2″,”2+3*2”]
Explanation: Both “2*3+2” and “2+3*2” evaluate to 8.

Example 3:
Input: num = “3456237490”, target = 9191
Output: []
Explanation: There are no expressions that can be created from “3456237490” to evaluate to 9191.

1. Expression Add Operators LeetCode Solution C++

class Solution {
private:
    void dfs(std::vector<string>& res, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
        if (pos == num.size() && cv == target) {
            res.push_back(cur);
        } else {
            for (int i=pos+1; i<=num.size(); i++) {
                string t = num.substr(pos, i-pos);
                long now = stol(t);
                if (to_string(now).size() != t.size()) continue;
                dfs(res, num, target, cur+'+'+t, i, cv+now, now, '+');
                dfs(res, num, target, cur+'-'+t, i, cv-now, now, '-');
                dfs(res, num, target, cur+'*'+t, i, (op == '-') ? cv+pv - pv*now : ((op == '+') ? cv-pv + pv*now : pv*now), pv*now, op);
            }
        }
    }

public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        if (num.empty()) return res;
        for (int i=1; i<=num.size(); i++) {
            string s = num.substr(0, i);
            long cur = stol(s);
            if (to_string(cur).size() != s.size()) continue;
            dfs(res, num, target, s, i, cur, cur, '#');
        }
        return res;
    }
};

2. Expression Add Operators LeetCode Solution Java

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> rst = new ArrayList<String>();
        if(num == null || num.length() == 0) return rst;
        helper(rst, "", num, target, 0, 0, 0);
        return rst;
    }
    public void helper(List<String> rst, String path, String num, int target, int pos, long eval, long multed){
        if(pos == num.length()){
            if(target == eval)
                rst.add(path);
            return;
        }
        for(int i = pos; i < num.length(); i++){
            if(i != pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            if(pos == 0){
                helper(rst, path + cur, num, target, i + 1, cur, cur);
            }
            else{
                helper(rst, path + "+" + cur, num, target, i + 1, eval + cur , cur);
                helper(rst, path + "-" + cur, num, target, i + 1, eval -cur, -cur);
                helper(rst, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
            }
        }
    }
}

3. Expression Add Operators Solution JavaScript

var addOperators = function(num, target) {
    const output = []
    function permute(str, arr, total, prev) {
        if(!str.length && total === target) output.push(arr.join(''));
        let len = str.length;
        if(str[0] === '0') len = 1;
        for(let i = 1; i <= len; i++) {
            const curr = +str.slice(0, i);
            const rest = str.slice(i);
            if(!arr.length) permute(rest, [curr], curr, curr);
            else {
                permute(rest, [...arr, '+', curr], total+curr, curr);
                permute(rest, [...arr, '-', curr], total-curr, 0-curr);
                const prod = prev * curr;
                permute(rest, [...arr, '*', curr], total-prev+prod, prod);
            }
        }
    }
    permute(num, [], 0, 0);
    return output;
};

4. Expression Add Operators Solution Python

class Solution(object):
    def addOperators(self, num, target):
        res, self.target = [], target
        for i in range(1,len(num)+1):
            if i == 1 or (i > 1 and num[0] != "0"):
                self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res)
        return res
    def dfs(self, num, temp, cur, last, res):
        if not num:
            if cur == self.target:
                res.append(temp)
            return
        for i in range(1, len(num)+1):
            val = num[:i]
            if i == 1 or (i > 1 and num[0] != "0"):
                self.dfs(num[i:], temp + "+" + val, cur+int(val), int(val), res)
                self.dfs(num[i:], temp + "-" + val, cur-int(val), -int(val), res)
                self.dfs(num[i:], temp + "*" + val, cur-last+last*int(val), last*int(val), res)