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 } }
执行结果如下: