Description
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.
Note that a number can contain multiple digits.
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.
Constraints:
1 <= num.length <= 10num consists of only digits.-231 <= target <= 231 - 1
Solutions
Solution 1
PythonJavaC#
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
def dfs(u, prev, curr, path):
if u == len(num):
if curr == target:
ans.append(path)
return
for i in range(u, len(num)):
if i != u and num[u] == '0':
break
next = int(num[u : i + 1])
if u == 0:
dfs(i + 1, next, next, path + str(next))
else:
dfs(i + 1, next, curr + next, path + "+" + str(next))
dfs(i + 1, -next, curr - next, path + "-" + str(next))
dfs(
i + 1,
prev * next,
curr - prev + prev * next,
path + "*" + str(next),
)
dfs(0, 0, 0, "")
return ans(code-box)
class Solution {
private List<String> ans;
private String num;
private int target;
public List<String> addOperators(String num, int target) {
ans = new ArrayList<>();
this.num = num;
this.target = target;
dfs(0, 0, 0, "");
return ans;
}
private void dfs(int u, long prev, long curr, String path) {
if (u == num.length()) {
if (curr == target) ans.add(path);
return;
}
for (int i = u; i < num.length(); i++) {
if (i != u && num.charAt(u) == '0') {
break;
}
long next = Long.parseLong(num.substring(u, i + 1));
if (u == 0) {
dfs(i + 1, next, next, path + next);
} else {
dfs(i + 1, next, curr + next, path + "+" + next);
dfs(i + 1, -next, curr - next, path + "-" + next);
dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
}
}
}
}(code-box)
using System;
using System.Collections.Generic;
public class Expression
{
public long Value;
public override string ToString()
{
return Value.ToString();
}
}
public class BinaryExpression : Expression
{
public char Operator;
public Expression LeftChild;
public Expression RightChild;
public override string ToString()
{
return string.Format("{0}{1}{2}", LeftChild, Operator, RightChild);
}
}
public class Solution {
public IList<string> AddOperators(string num, int target) {
var results = new List<string>();
if (string.IsNullOrEmpty(num)) return results;
this.num = num;
this.results = new List<Expression>[num.Length, num.Length, 3];
foreach (var ex in Search(0, num.Length - 1, 0))
{
if (ex.Value == target)
{
results.Add(ex.ToString());
}
}
return results;
}
private string num;
private List<Expression>[,,] results;
private List<Expression> Search(int left, int right, int level)
{
if (results[left, right, level] != null)
{
return results[left, right, level];
}
var result = new List<Expression>();
if (level < 2)
{
for (var i = left + 1; i <= right; ++i)
{
List<Expression> leftResult, rightResult;
leftResult = Search(left, i - 1, level);
rightResult = Search(i, right, level + 1);
foreach (var l in leftResult)
{
foreach (var r in rightResult)
{
var newObjects = new List<Tuple<char, long>>();
if (level == 0)
{
newObjects.Add(Tuple.Create('+', l.Value + r.Value));
newObjects.Add(Tuple.Create('-', l.Value - r.Value));
}
else
{
newObjects.Add(Tuple.Create('*', l.Value * r.Value));
}
foreach (var newObject in newObjects)
{
result.Add(new BinaryExpression
{
Value = newObject.Item2,
Operator = newObject.Item1,
LeftChild = l,
RightChild = r
});
}
}
}
}
}
else
{
if (left == right || num[left] != '0')
{
long x = 0;
for (var i = left; i <= right; ++i)
{
x = x * 10 + num[i] - '0';
}
result.Add(new Expression
{
Value = x
});
}
}
if (level < 2)
{
result.AddRange(Search(left, right, level + 1));
}
return results[left, right, level] = result;
}
}(code-box)
