<p>2021-02-18：给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文。arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。返回需要至少多少张贴纸可以完成这个任务。例子：str= "babac"，arr = {"ba","c","abcd"}。a + ba + c 3 abcd + abcd 2 abcd+ba 2。所以返回2。</p><p/><p>福哥答案2021-02-18：</p><p>自然智慧即可。</p><p>带记忆的递归。对“babac”排序，变成“aabbc”，然后根据数组，依次消掉a，然后b，最后c，这是一个优化点。有代码。</p><p>代码用golang编写，代码如下：</p><p/><p>go</p><p>package main</p><p/><p>import (</p><p> "fmt"</p><p> "strings"</p><p>)</p><p/><p>const MAX = int(^uint(0) >> 1) //构造0111111111.... 9223372036854775807</p><p>const MIN = int(^MAX) //构造10000000... -9223372036854775808</p><p>func main() {</p><p> ret := minStickers([]string{"ba", "c", "abcd"}, "babac")</p><p> fmt.Println(ret)</p><p>}</p><p/><p>func minStickers(stickers []string, target string) int {</p><p> N := len(stickers)</p><p> counts := make([][]int, N)</p><p> for i := 0; i < N; i++ {</p><p> counts[i] = make([]int, 26)</p><p> }</p><p> for i := 0; i < N; i++ {</p><p> str := stickers[i]</p><p> for _, cha := range str {</p><p> counts[i][cha-'a']++</p><p> }</p><p> }</p><p> dp := make(map[string]int)</p><p> dp[""] = 0</p><p> ans := process(counts, target, dp)</p><p> if ans == MAX {</p><p> return -1</p><p> } else {</p><p> return ans</p><p> }</p><p>}</p><p>func process(stickers [][]int, t string, dp map[string]int) int {</p><p/><p> if _, ok := dp[t]; ok {</p><p> return dp[t]</p><p> }</p><p> tcounts := make([]int, 26)</p><p> for _, cha := range t {</p><p> tcounts[cha-'a']++</p><p> }</p><p> N := len(stickers)</p><p> min := MAX</p><p> for i := 0; i < N; i++ {</p><p> sticker := stickers[i]</p><p> if sticker[t[0]-'a'] > 0 {</p><p> builder := strings.Builder{}</p><p> for j := 0; j < 26; j++ {</p><p> if tcounts[j] > 0 {</p><p> nums := tcounts[j] - sticker[j]</p><p> for k := 0; k < nums; k++ {</p><p> builder.WriteByte('a' + byte(j))</p><p> }</p><p> }</p><p> }</p><p> rest := builder.String()</p><p> min = getMin(min, process(stickers, rest, dp))</p><p> }</p><p> }</p><p> ans := min</p><p> if min != MAX {</p><p> ans++</p><p> }</p><p> dp[t] = ans</p><p> return ans</p><p>}</p><p>func getMin(a int, b int) int {</p><p> if a < b {</p><p> return a</p><p> } else {</p><p> return b</p><p> }</p><p>}</p><p></p><p>执行结果如下：</p><p class="image-package"><img class="uploaded-img" src="https://upload-images.jianshu.io/upload_images/22862325-054ab5fef8a193da.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" width="auto" height="auto"/></p><p/><p>***</p><p>左神java代码</p><p>评论</p><p>
</p>
有疑问加站长微信联系（非本文作者）
