Python with eval (no TLE)


  • 0
    A
    import re
    class Solution(object):
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            memo = {}
            def memo_eval(s):
                if s not in memo:
                    memo[s] = eval(s)
                return memo[s]
            def dfs(res_s, cur_v, prv_s, idx):
                if idx == len(num):
                    if cur_v == target:
                        res.append(res_s)
                    return
                if idx == 0:  # can't append any op before the 1st char,  note that memo_eval('') is invalid
                    dfs(res_s+num[idx], cur_v + memo_eval(prv_s+num[idx]), prv_s+num[idx], idx + 1)
                    return
                if re.split('-|\*', prv_s)[-1][0] != '0':
                    dfs(res_s+num[idx], cur_v - memo_eval(prv_s) + memo_eval(prv_s+num[idx]), prv_s+num[idx], idx + 1)  # no op
                dfs(res_s+'+'+num[idx], cur_v + memo_eval(num[idx]), num[idx], idx + 1)  # '+'
                dfs(res_s+'-'+num[idx], cur_v + memo_eval('-'+num[idx]), '-'+num[idx], idx + 1)  # '-'
                dfs(res_s+'*'+num[idx], cur_v - memo_eval(prv_s) + memo_eval(prv_s+'*'+num[idx]), prv_s+'*'+num[idx], idx + 1)  # '*'
                
            res = []
            dfs('', 0, '', 0)
            return res
    

Log in to reply
 

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