#Code

1 messages · Page 1 of 1 (latest)

solemn slate
# 
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        return solution(num, target)
    
'''
Backtrack
O(4^n) time and space for considering all possible combinations between each digit (blank, +, -, or *)
'''
def solution(nums, target):
    def backtrack(startIdx, path, curSum, prevNum):
        if startIdx == n and curSum == target:
            res.append(path)
            return
        
        for i in range(startIdx, n):
            # Avoid leading zeroes edge cases
            if i > startIdx and nums[startIdx] == '0':
                return
            
            # Slice number
            num = int(nums[startIdx:i+1])
            
            # No leading signs
            if startIdx == 0:
                backtrack(i + 1, str(num), curSum + num, num)
            else:
                backtrack(i + 1, path + '+' + str(num), curSum + num, num)
                backtrack(i + 1, path + '-' + str(num), curSum - num, -num)
                backtrack(i + 1, path + '*' + str(num), curSum - prevNum + num * prevNum, num * prevNum)
    
    n = len(nums)
    path = ''
    res = []
    
    backtrack(0, path, 0, 0)
    
    return res
agile carbon
#

how do you evaluate currSum

solemn slate
#

if curSum is equal to target, that means we find a valid path, append that to res
Otherwise
In add, we just add curSum with num
In subtract, we subtract curSum with num, set num to negative
In multiply, we remove the prevNum we add/subtract to curSum, and add prevNum * num. Update prevNum to num*prevNum

agile carbon
#

and you avoid leading 0's cuz i > startIdx?

#

that solution is so much better than mine lol

solemn slate
#

yeahh

#

if nums[startIdx] is 0, then we want to do our operations for that digit only bc otherwise if we add further digits (i > startIdx) it will be leading zeros

#

thats the solution i got from my nuro phone

agile carbon
#

I agree then, this solution makes it seem like a medium lol

#

I was doing it way more complicated which made it way harder

solemn slate
#

its ok