【Python】递归之拼接字符串

思路：

• 确定递归出口：target判断完毕，返回0
• 利用了Counter函数
  • Counter(a) & Counter(b)判断交集
  • Counter(a) - Counter(b)获得差集
• 对stickers构建couter字典，遍历stickers，逐个匹配target，返回最小匹配次数

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        @cache
        def dfs(rest):
            if not rest:
                return 0
            ans = 1e20
            rest_dic = Counter(rest)
            for i in range(N):
                # 判断模式串和目标串是否有交集
                if dic[i] & rest_dic:
                    # 获得删除字符后的字符串
                    rest = "".join(k * v for k, v in (rest_dic - dic[i]).items())
                    # 如果之后没有匹配成功，rest没有置0，则ans=1e20
                    ans = min(ans, dfs(rest)+1)
            return ans

        N = len(stickers)
        dic = [Counter(s) for s in stickers]        
        res = dfs(target) 
        return res if res != 1e20 else -1

691. 贴纸拼词

https://leetcode.cn/problems/stickers-to-spell-word/submissions/