2021-02-18：给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文。arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。返回需要至少多少张贴纸可以完成这个任务。例子：str= "babac"，arr = {"ba","c","abcd"}。a + ba + c 3 abcd + abcd 2 abcd+ba 2。所以返回2。
福哥答案2021-02-18：
自然智慧即可。
带记忆的递归。对“babac”排序，变成“aabbc”，然后根据数组，依次消掉a，然后b，最后c，这是一个优化点。有代码。
代码用golang编写，代码如下：
package main
import (
"fmt"
"strings"
)
const MAX = int(^uint(0) >> 1) //构造0111111111.... 9223372036854775807
const MIN = int(^MAX) //构造10000000... -9223372036854775808
func main() {
ret := minStickers([]string{"ba", "c", "abcd"}, "babac")
fmt.Println(ret)
}
func minStickers(stickers []string, target string) int {
N := len(stickers)
counts := make([][]int, N)
for i := 0; i < N; i++ {
counts[i] = make([]int, 26)
}
for i := 0; i < N; i++ {
str := stickers[i]
for _, cha := range str {
counts[i][cha-'a']++
}
}
dp := make(map[string]int)
dp[""] = 0
ans := process(counts, target, dp)
if ans == MAX {
return -1
} else {
return ans
}
}
func process(stickers [][]int, t string, dp map[string]int) int {
if _, ok := dp[t]; ok {
return dp[t]
}
tcounts := make([]int, 26)
for _, cha := range t {
tcounts[cha-'a']++
}
N := len(stickers)
min := MAX
for i := 0; i < N; i++ {
sticker := stickers[i]
if sticker[t[0]-'a'] > 0 {
builder := strings.Builder{}
for j := 0; j < 26; j++ {
if tcounts[j] > 0 {
nums := tcounts[j] - sticker[j]
for k := 0; k < nums; k++ {
builder.WriteByte('a' + byte(j))
}
}
}
rest := builder.String()
min = getMin(min, process(stickers, rest, dp))
}
}
ans := min
if min != MAX {
ans++
}
dp[t] = ans
return ans
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
图片
