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 mainimport ( "fmt" "strings")const MAX = int(^uint(0) >> 1) //结构0111111111.... 9223372036854775807const MIN = int(^MAX) //结构10000000... -9223372036854775808func 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 }}执行后果如下：
左神java代码
评论