2021-02-18：給定一個字符串str，給定一個字符串類型的數(shù)組arr，
2021-02-18：給定一個字符串str，給定一個字符串類型的數(shù)組arr，出現(xiàn)的字符都是小寫英文。arr每一個字符串，代表一張貼紙，你可以把單個字符剪開使用，目的是拼出str來。返回需要至少多少張貼紙可以完成這個任務(wù)。例子：str= "babac"，arr = {"ba","c","abcd"}。a + ba + c? 3? abcd + abcd 2? abcd+ba 2。所以返回2。
福哥答案2021-02-18：
自然智慧即可。
帶記憶的遞歸。對“babac”排序，變成“aabbc”，然后根據(jù)數(shù)組，依次消掉a，然后b，最后c，這是一個優(yōu)化點。有代碼。
代碼用golang編寫，代碼如下：
```go
package main
import (
? ? "fmt"
? ? "strings"
)
const MAX = int(^uint(0) >> 1) //構(gòu)造0111111111....? ?9223372036854775807
const MIN = int(^MAX)? ? ? ? ? //構(gòu)造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
? ? }
}
```
執(zhí)行結(jié)果如下：
***
[左神java代碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class19/Code03_StickersToSpellWord.java)
[評論](https://user.qzone.qq.com/3182319461/blog/1613604412)
