关于福大大架构师每日一题:20210218给定一个字符串str给定一个字符串类型的数组arr出现的字符都是小写英文arr每一个字符串

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

执行后果如下：

左神 java 代码
评论