Last updated on October 6th, 2024 at 02:03 pm
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
Table of Contents
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)