My DFS Code . (Python)


  • 0
    Y
    def minStickers(self, stickers, target):
            m = collections.Counter(target)
            ret = [(1 << 31) - 1]#A Big Number   
            def dfs(_m, c, i):
                if i == len(target):
                    ret[0] = min(ret[0], c)
                    return
                if _m[target[i]] >= m[target[i]]:
                    dfs(_m, c, i + 1)
                    return
                if c >= ret[0]-1:#Here is  {ret[0]-1} not {ret[0]} because of the next loop {c} will add 1
                    return
                for j in stickers:
                    if target[i] in j:
                        for n in j:
                            _m[n] += 1
                        dfs(_m, c + 1, i + 1)
                        for n in j:
                            _m[n] -= 1
    
            dfs(collections.defaultdict(int), 0, 0)
            if ret[0]==(1 << 31) - 1:
                return -1
            return ret[0]
    

Log in to reply
 

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