golang刷leetcode：贴纸拼词
golang刷leetcode：贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
示例 1：
输入：stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
示例 2:
输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。
提示:
n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target <= 15
stickers[i] 和 target 由小写英文单词组成
解题思路：
1，首先我们看下如何拆分子问题，本题不是从左往右，也不是区间的拆分，而是枚举拆分：sticker可以替换target的任意位置。
2，因此我们的子问题是；target被任意个sticker替换后，剩余的部分
3，假设target长度为m，那么target的子串个数为2 ^m个，每个位置右包含当前字母和不包含当前字母两种情况。
4，我们用替换掉sticker后剩余的部分继续替换，直到剩余部分为空，说明我们找到了一个解
5，那么最差的解就是m个sticker，说一超出m的拼接方式一定不是问题的解，说明没法拼接。
6，如何表示剩余部分呢？因为每个位置右两种选择，所以可以考虑用二进制位来表示。所以每个子串可以用整数表示。
7，相应的，我们的target，就是m位都是1的整数，即2^m- 1
8，用一个长度为2 ^m数组dp来记录每一个子串可以由stickers拼接的最小长度
9，我们的目标就是dp[2^m- 1]
10，假设sticker长度为n，我们有个子函数f，可以把dp[i]和sticker[ j]中对应的 相同字母的位清0:比如sticker[j]中有一个a，3个b，1个c；dp[i]是abdbe；处理完我们得到de
11，问题就转化成了我们常见的0 k背包问题
12，对于每一个物品sticker[ j]，最多可以尝试的次数是 while（f（dp[i],sticker[j]）!=dp[i]）循环的次数k，和m两张之间的小值，显然前者小
13，边界条件是dp[0]=0,调用f k次后剩余部分假如是left，dp[left]=0;其他情况是-1，可以初始化为m+1
14,状态转移方程是，dp[i]=min(dp[f(dp[i],sticker[j])]+1)
15,其中i=0～2^m- 1] ；j=0～n;p=0~k
首选我们看下递归解：
其中subStrMatch就是我们所说的方法f
func minStickers(stickers []string, target string) int {
m := len(target)
f := make([]int, 1<<m)
for i := range f {
f[i] = -1
}
f[0] = 0
var dp func(int) int
dp = func(mask int) int {
if f[mask] != -1 {
return f[mask]
}
f[mask] = m + 1
for _, sticker := range stickers {
left:=subStrMatch(mask,sticker,target)
if left < mask {
f[mask] = min(f[mask], dp(left)+1)
}
}
return f[mask]
}
ans := dp(1<<m - 1)
if ans <= m {
return ans
}
return -1
}
func subStrMatch(mask int,sticker,target string)int{
left := mask
cnt := [26]int{}
for _, c := range sticker {
cnt[c-'a']++
}
for i, c := range target {
if mask>>i&1 == 1 && cnt[c-'a'] > 0 {
cnt[c-'a']--
left ^= 1 << i
}
}
return left
}
func min(a, b int) int {
if a > b {
return b
}
return a
}动态规划方法
func minStickers(stickers []string, target string) int {
m := len(target)
f := make([]int, 1<<m)
for i := range f {
f[i] = m+1
}
f[0] = 0
//预处理数组，0，k背包的k，
//每个sticker最多可以选择的个数
k:=make([]int,len(stickers))
for i, sticker := range stickers {
mask:=0
left:=1<<m - 1
cnt:=0
for left!=mask{
mask=left
left=subStrMatch(mask,sticker,target)
cnt++
}
k[i]=cnt
}
for i:=0;i<1<<m;i++{
for j, sticker := range stickers {
left:=i
for h:=0;h<k[j];h++{
left:=subStrMatch(left,sticker,target)
if left < i {
f[i] = min(f[i], f[left]+1)
}
}
}
}
ans := f[1<<m - 1]
if ans <= m {
return ans
}
return -1
}
func subStrMatch(mask int,sticker,target string)int{
left := mask
cnt := [26]int{}
for _, c := range sticker {
cnt[c-'a']++
}
for i, c := range target {
if mask>>i&1 == 1 && cnt[c-'a'] > 0 {
cnt[c-'a']--
left ^= 1 << i
}
}
return left
}
func min(a, b int) int {
if a > b {
return b
}
return a
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
