H-691. Stickers to Spell Word

Loading...LeetCode

class Solution:
    def minStickers(self, stickers, target):
        # cnt是当前target每个字符出现次数的字典
        # res是当前最少需要的stickers数量
        # n是target长度
        cnt, res, n = collections.Counter(target), float("inf"), len(target)  
        
        # dic是当前选中的所有stickers的字符组成的字典, key是字符, value是出现次数
        # used是当前使用的stickers的数量
        # i是当前正在判断的target的下标(即, 也可以理解为一个指针)
        def dfs(dic, used, i):
        
            # 因为res在函数里被赋值, 且不是mutable, 所以需要声明nonlocal 
            # 详见: https://docs.python.org/3/faq/programming.html#why-am-i-getting-an-unboundlocalerror-when-the-variable-has-a-value
            nonlocal res
            
            # 如果指针指向第n位, 说明判断结束
            if i == n: 
                res = used
                
            # 如果在判断第i位的时候, 根据此时已经选出来的stickers构造的
            # 的dic中, target[i]这个字符的数量已经大于等于cnt中这个字符的数量,
            # 我们直接判断target的下一位
            elif dic[target[i]] >= cnt[target[i]]: 
                dfs(dic, used, i + 1)
                
            # 1. 从stickers里面选择一个sticker, 
            # 如果target[i]存在于此sticker里, 我们用它继续构造
            # dic. 接着我们递归调用. 递归出来之后, 记得从dic中
            # 删除它.
            # 2. 注意入口条件是used < res - 1 因为进入这个循环之后,
            # 要么target[i]不在sticker里面, 则进了相当于没进
            # 要么target[i]在sticker里面, 此时我们需要把这个sticker加入
            # dic里, 然后used + 1, 如果此时used + 1等于res, 那么可以预见, 
            # 最终通过这条路径选出来的res_2是要大于等于当前res的, 所以
            # 我们本来可以不必进入这条路径的.
            # 所以我们只允许当used + 1 < res的时候进来.(这样可以少计算很多)
            elif used + 1 < res:
                for sticker in stickers:
                    if target[i] in sticker:
                        for s in sticker: 
                            dic[s] += 1
                        dfs(dic, used + 1, i + 1)
                        for s in sticker: 
                            dic[s] -= 1
                        
        dfs(collections.defaultdict(int), 0, 0)
        return res if res < float("inf") else -1