python dp solution


  • 1
    S
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        if len(num) == 0:
            return [''] if target == 0 else []
    
        v, val = num[0], int(num[0])
        # value, strexp, last_num, last_factor
        dp = [[(val, v, val, val)]]
        for i in range(1, len(num)):
            v, val = num[i], int(num[i])
            dp_p = dp[-1]
            dp.append([])
            for e in dp_p:
                dp[-1].append((e[0] + val, e[1] + '+' + v, val, val))
                dp[-1].append((e[0] - val, e[1] + '-' + v, val, -val))
                # 1+2*3
                dp[-1].append((e[0] + e[3] * (val - 1), e[1] + '*' + v, val, e[3] * val))
                # 1+2*34
                if e[2] == 0: continue
                f_head = e[3] / e[2]
                f_tail = e[2] * 10 + val
                dp[-1].append((e[0] - e[3] + f_head * f_tail, e[1] + v, f_tail, f_head * f_tail))
    
        return map(lambda e: e[1], filter(lambda e: e[0] == target, dp[-1]))

Log in to reply
 

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