Python Fast and Elegant Solution Beats 90%


  • 0
    D
    class Solution(object):
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            n = len(num)
            if n == 0: return []
            ans = []        
            # Step 2: compose [digit] into a validated string
            def compose(arr):
                total = len(arr)
                def collect(i, pre, val):
                    if i >= total:
                        if val == target: ans.append(pre.lstrip('+'))
                    else:
                        collect(i+1, pre+"+"+str(arr[i]), val + arr[i])
                        if i > 0: collect(i+1, pre+"-"+str(arr[i]), val - arr[i])
                        product = arr[i]
                        candidates = []
                        s = str(arr[i])
                        for j in range(i+1, total):
                            product *= arr[j]
                            s += '*'+str(arr[j])
                            candidates.append((j+1, s, product))
                        for c in candidates:
                            collect(c[0], pre + '+' + c[1], c[2]+val)
                            if i>0: collect(c[0], pre + '-' + c[1], -c[2]+val)
                collect(0, '', 0)
                
            
            
            # Step 1: decompose num into [digit]
            def decompose(i, curr):
                if i >= n: compose(curr)
                else:
                    if num[i] == '0': decompose(i+1, curr + [0])
                    else:
                        for j in range(i+1, n+1):
                            decompose(j, curr + [int(num[i:j])])
            
            
            decompose(0, [])
            return ans

Log in to reply
 

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