<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>&nbsp; &nbsp; &quot;fmt&quot;</p><p>&nbsp; &nbsp; &quot;strings&quot;</p><p>)</p><p/><p>const MAX = int(^uint(0) &gt;&gt; 1) //构造0111111111....&nbsp; &nbsp;9223372036854775807</p><p>const MIN = int(^MAX)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //构造10000000...&nbsp; &nbsp;-9223372036854775808</p><p>func main() {</p><p>&nbsp; &nbsp; ret := minStickers([]string{&quot;ba&quot;, &quot;c&quot;, &quot;abcd&quot;}, &quot;babac&quot;)</p><p>&nbsp; &nbsp; fmt.Println(ret)</p><p>}</p><p/><p>func minStickers(stickers []string, target string) int {</p><p>&nbsp; &nbsp; N := len(stickers)</p><p>&nbsp; &nbsp; counts := make([][]int, N)</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; counts[i] = make([]int, 26)</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; str := stickers[i]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; for _, cha := range str {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counts[i][cha-&#39;a&#39;]++</p><p>&nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; dp := make(map[string]int)</p><p>&nbsp; &nbsp; dp[&quot;&quot;] = 0</p><p>&nbsp; &nbsp; ans := process(counts, target, dp)</p><p>&nbsp; &nbsp; if ans == MAX {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return -1</p><p>&nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return ans</p><p>&nbsp; &nbsp; }</p><p>}</p><p>func process(stickers [][]int, t string, dp map[string]int) int {</p><p/><p>&nbsp; &nbsp; if _, ok := dp[t]; ok {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return dp[t]</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; tcounts := make([]int, 26)</p><p>&nbsp; &nbsp; for _, cha := range t {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; tcounts[cha-&#39;a&#39;]++</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; N := len(stickers)</p><p>&nbsp; &nbsp; min := MAX</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; sticker := stickers[i]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; if sticker[t[0]-&#39;a&#39;] &gt; 0 {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; builder := strings.Builder{}</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j &lt; 26; j++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if tcounts[j] &gt; 0 {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nums := tcounts[j] - sticker[j]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for k := 0; k &lt; nums; k++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; builder.WriteByte(&#39;a&#39; + byte(j))</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rest := builder.String()</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = getMin(min, process(stickers, rest, dp))</p><p>&nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; ans := min</p><p>&nbsp; &nbsp; if min != MAX {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; ans++</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; dp[t] = ans</p><p>&nbsp; &nbsp; return ans</p><p>}</p><p>func getMin(a int, b int) int {</p><p>&nbsp; &nbsp; if a &lt; b {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return a</p><p>&nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return b</p><p>&nbsp; &nbsp; }</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>