Problem: Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates to the target value.
Example:
Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"]
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"]
Input: num = "105", target = 5 Output: ["1*0+5","10-5"]
Input: num = "00", target = 0 Output: ["0*0","0+0","0-0"]
Input: num = "3456237490", target = 9191 Output: []
Approach: This is a backtracking problem (with no shortcuts :)). Here we will try every combination that is to put +, - and * operators and see if the calculated value is the target or not. This problems looks simple initially but there are problems:
We can combine multiple digits to make one operand like in the third example from "105" we have one combination which 10 - 5. How to deal with this? I would say we will make it our 4th operator and this operator works like follows:
current_operand = current_operand * 10 + num[current_index]
We just need to take care of numbers like "05" etc.
The second problem is because of '*' operation, we just can't calculate expression value on the fly like (1 + 2 * 3), if we try to do it on the fly then we will be calculating something like following:
1 + 2 = 3
3 * 3 = 9
The above calculation is clearly wrong as the expression value is 7. How do we calculate it, then?
To do this we need to keep track of the previous operand. Let's see how it helps:
0 + 1 = 1 | prev = +1
1 + 2 = 3 | prev = +2
1 + 2 * 3 = (3 - 2) + ( 2 * 3) = 7 | prev = +6
So the formula is (current_result - previous_operand) + (previous_operand * current_operand)
Let's see with another example 4 * 2 - 10 * 3:
0 + 4 = 4 | prev = +4
4 * 2 = (4 - 4) + ( 4 * 2) = 8 | prev = +8
4 * 2 - 10 = 8 - 10 = -2 | prev = -10
4 * 2 - 10 * 3 = (-2 - (-10) + (-10 * 3) = 8 - 30 = 22 | prev = -30
Now we have dealt with both the problems and we are ready for our implementation.
Implementation in C#:
public IList<string> AddOperators(string num, int target)
{
if (num.Length == 0)
{
return new List<string>();
}
List<string> result = new List<string>();
List<string> ops = new List<string>();
this.AddOperatorsRecurse(num, target, result, 0, 0, 0, 0, ops);
return result;
}
public void AddOperatorsRecurse(
string num,
int target,
List<string> result,
int currIndex,
long currOperand,
long prevOperand,
long currResult,
List<string> ops)
{
if (currIndex == num.Length)
{
if (currResult == target && currOperand == 0)
{
StringBuilder sb = new StringBuilder();
for (int i = 1; i < ops.Count; ++i)
{
sb.Append(ops[i]);
}
result.Add(sb.ToString());
}
return;
}
// Add next digit to current operand
currOperand = currOperand * 10 + long.Parse(num[currIndex].ToString());
// To take care of 05,00 etc
if (currOperand > 0)
{
this.AddOperatorsRecurse(num, target, result, currIndex + 1, currOperand, prevOperand, currResult, ops);
}
// Add
ops.Add("+");
ops.Add(currOperand.ToString());
this.AddOperatorsRecurse(
num,
target,
result,
currIndex + 1,
0,
currOperand,
currResult + currOperand,
ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
if (ops.Count > 0)
{
// Subtract
ops.Add("-");
ops.Add(currOperand.ToString());
this.AddOperatorsRecurse(
num,
target,
result,
currIndex + 1,
0,
-currOperand,
currResult - currOperand,
ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
// Multiplication
ops.Add("*");
ops.Add(currOperand.ToString());
this.AddOperatorsRecurse(
num,
target,
result,
currIndex + 1,
0,
currOperand * prevOperand,
currResult - prevOperand + (currOperand * prevOperand),
ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
}
}
Complexity: Given we have 4 recursive paths(operators) and every recursive path ends when index reached to the end of the string, our complexity is 4^n. We are also joining the whole ops which can be of 2 * n size at worse so our complexity is O(n * 4^n)
No comments:
Post a Comment