The problem is stated as: Given a string that contains only digits 0-9 and a target value, return all expressions that are created by adding some binary operators (+, -, or *) between the digits so they evaluate to the target value. In some cases there may not be any binary operators that will create valid expressions, in which case the function should return an empty array. The numbers in the new expressions should not contain leading zeros.
The function should return all valid expressions that evaluate to target, sorted lexicographically.
For example:
digits = "123"
and target = 6
, should return: ["1*2*3", "1+2+3"]
My current algorithm is below. I optimized it as much as I can. The question is base on code fights. My algo will generate all combinations of operands and operators accordingly. For the example above, it'll generate:
Operands:
[['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]
Operators:
{0: [()], 1: [('+',), ('-',), ('*',)], 2: [('+', '+'), ('+', '-'), ('+', '*'), ('-', '+'), ('-', '-'), ('-', '*'), ('*', '+'), ('*', '-'), ('*', '*')]}
It then combines all possible combinations of operands and operators and evaluate each.
For digits = "1234506789"
and target = 6
, it takes about 2.2 secs. It should be enough for code fights that has a limit of 4 sec, but I guess that also depends on the speed of the processor. But for some reason it still hits the time limit from the site. Thus Im trying to see how it can be optimized a bit more.
Restrictions are:
2 <= digits.length <= 10
-10^4 <= target <= 10^4
My code is below. I commented out some of the alternatives I used, which pretty much has the same speed though.
from itertools import combinations, permutations
import itertools
import time
def getExpression(digits, target):
operation = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
}
seen = {}
def calculate2(e,sign):
e = list(e)
sign = list(sign)
operands = [int(e.pop())]
operators = []
for i in reversed(range(len(sign))):
operator = sign[i]
if operator == '*':
operators.append(operator)
operands.append(int(e[i]))
elif operator == '+' or operator == '-':
while operators and operators[-1] == '*':
compute(operands, operators)
operators.append(operator)
operands.append(int(e[i]))
while operators:
compute(operands, operators)
return operands[-1]
def compute(operands, operators): ## PERFORMS MATHEMATICAL OP.
left, right = operands.pop(), operands.pop()
op = operators.pop()
operands.append(operation[op](left,right))
## BELOW ALSO HAS SIMILAR SPEED
# if op == '+':
# operands.append(left + right)
# elif op == '-':
# operands.append(left - right)
# elif op == '*':
# operands.append(left * right)
## USING A HASH TABLE IMPLEMENTATION. BASICALLY DONT CALCULATE IF IT WAS CALCULATED BEFORE
## BUT WITH ALL THE OVERHEAD NECESSARY, TAKES MORE TIME AND SPACE
# if op == '+':
# seenKey = str(left) + "+" + str(right)
# key = seen.get(seenKey)
# if key:
# operands.append(key)
# else:
# val = left + right
# operands.append(val)
# seen[seenKey] = val
# elif op == '-':
# seenKey = str(left) + "-" + str(right)
# key = seen.get(seenKey)
# if key:
# operands.append(key)
# else:
# val = left - right
# operands.append(val)
# seen[seenKey] = val
# elif op == '*':
# seenKey = str(left) + "*" + str(right)
# key = seen.get(seenKey)
# if key:
# operands.append(key)
# else:
# val = left * right
# operands.append(val)
# seen[seenKey] = val
def isValid(e): ## DIGITS WITH LEADING 0 IS NOT VALID
valid = True
for num in e:
if num[0] == '0' and len(num) > 1:
valid = False
break
return valid
def getStringForm(e,sign): ## RETURNS STRING FORMAT
temp = ""
for num, operator in zip(e, sign):
temp += num
temp += operator
temp += e[-1]
return temp
def getSign_combination(length): ## GET ALL COMBO OF +,-,*
signCombo = {}
for i in range(0, length):
signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
return signCombo
def generate_combination(source, comb): ## GET ALL COMBO OF DIGITS
res = []
for x, action in zip(source, comb + (0,)):
res.append(x)
if action == 0:
yield "".join(res)
res = []
## STRING OR LIST (ABOVE) SEEMS TO BE THE SAME EFFICIENCY FOR THIS EXAMPLE
# res = ""
# for x, action in zip(source, comb + (0,)):
# res += x
# if action == 0:
# yield res
# res = ""
elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]
signCombo = getSign_combination(len(digits))
## THIS IS USING LIST COMPREHENSION, SHOULD BE FASTER BUT SEEMS THE SAME (BELOW MAY EVEN BE FASTER)
return sorted([ getStringForm(e, sign) for e in elementCombo if isValid(e) for i,sign in enumerate(signCombo[len(e)-1]) if calculate2(e,sign) == target ])
## BELOW ALSO HAS SIMILAR SPEED MAYBE EVEN A LITTLE FASTER THAN THE LIST COMPREHENSION ABOVE
# result = []
# for e in elementCombo:
# if isValid(e):
# signs = signCombo[len(e)-1]
# for i,sign in enumerate(signs):
# if calculate2(e, sign) == target:
# result.append(getStringForm(e, sign))
# return sorted(result)
digits = "1234506789"
target = 6
start = time.clock()
print("Answer:", getExpression(digits, target))
print(time.clock() - start)