My DFS Code . (Python)


  • 1
    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]
    

  • 0
    L

    Have you thought about using memo? I was trying to do something similar, but ran into TLE and couldn't figure out a way to memoize

    class Solution(object):
        def minStickers(self, stickers, target):
            """
            :type stickers: List[str]
            :type target: str
            :rtype: int
            """
            mi=[float("inf")]
            def dfs(stickers,d,missing,su,path):
                for i,s in enumerate(stickers):
                    need=d.copy()
                    pre=missing
                    for c in s:
                        missing-=need[c]>0
                        need[c]-=1          
                        if pre!=missing and not missing:
                            mi[0]=min(mi[0],su+1)
                            return        
                    if pre!=missing:
                        dfs(stickers,need,missing,su+1,path+[s])
                        missing=pre
                    else:
                        dfs(stickers[:i]+stickers[i+1:],need,missing,su,path)           
            dfs(stickers,collections.Counter(target),len(target),0,[])
            return mi[0] if mi[0]!=float("inf") else -1

Log in to reply
 

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