2021-02-18：给定一个字符串str，给定一个字符串类

原创

福大大架构师每日一题

修改于 2021-02-19 10:02:39

4870

修改于 2021-02-19 10:02:39

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
    }
}

执行结果如下：