Python dfs accepted


  • -3
    A
    class Solution(object):
        def addOperators(self, num, target):
            """
            :type num: str
            :type target: int
            :rtype: List[str]
            """
            fn = []
            self.dfs(num, "", 0, 0,fn, target, len(num))
            return fn
        
    
        def dfs(self, sb, sv, zhi, chengshu, finalist, target, lennum):        
            if len(sb) == 0:        
                if zhi == target:                
                    finalist.append(sv)
                return
    
            for i in range(len(sb)):            
                tsb = sb[0:i+1]
                if len(tsb) == 2 and tsb[1] == "0":break 
                if len(sb) == lennum:
                    self.dfs(sb[i+1:], tsb, zhi+int(tsb), int(tsb), finalist, target, lennum)                            
                else:         
                    self.dfs(sb[i+1:], sv + "+" + tsb, zhi+int(tsb), int(tsb), finalist, target, lennum)
                    self.dfs(sb[i+1:], sv + "-" + tsb, zhi-int(tsb), -int(tsb), finalist, target, lennum)
                    self.dfs(sb[i+1:], sv + "*" + tsb, zhi-chengshu+chengshu*int(tsb), chengshu*int(tsb), finalist, target, lennum)

  • 0
    S

    Could you please share your run time?


  • 0
    C

    one line is wrong and this is correct:
    if len(tsb) >= 2 and tsb[0] == "0":break

    break because there can't be leading zeros.


Log in to reply
 

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