Python solution 26 lines


  • 0
    Y
    class Solution(object):
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            result = []
            def findExpression(expr, num, diff, currentVal):
                if len(num) == 0 and currentVal == target:
                   result.append(expr)
                else:  
                   num_len = len(num)    
                   for i in range(num_len):
                       nextDiff = int(num[:i+1])
                       if len(str(nextDiff)) != i+1:
                          return  
                       findExpression(expr+'+'+num[:i+1], num[i+1:], nextDiff, currentVal+nextDiff)
                       findExpression(expr+'-'+num[:i+1], num[i+1:], -nextDiff, currentVal-nextDiff)
                       findExpression(expr+'*'+num[:i+1], num[i+1:], diff*nextDiff,(currentVal-diff)+diff*nextDiff)
            n = len(num)                    
            for i in range(n):
                if len(str(int(num[:i+1]))) != i+1:
                   continue  
                findExpression(num[:i+1], num[i+1:], int(num[:i+1]), int(num[:i+1]))
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.