2021-02-18: Given a string STR, given an array arr of string type, the characters appear in lowercase English. Arr each string, representing a sticker, you can cut out individual characters to use,

2021-02-18: Given a string STR, given an array arr of string type, the characters appear in lowercase English. Arr Each string, representing a sticker, you can cut out individual characters to make STR. Returns the minimum number of stickers needed to complete the task. Example: STR = “babac”, arr = {“ba”,”c”,”abcd”}. A + BA + c 3 ABCD + abcd 2 abcd+ BA 2. So return 2.

Fogg answer 2021-02-18: Natural wisdom. Recursion with memory. Sort “babac” to “aabbc”, and then eliminate a, then B, and finally C, according to the array, which is an optimization point. With the code. The code is written in Golang, and the code is as follows:

package main

import (
    "fmt"
    "strings"
)

const MAX = int(^uint(0) > >1) / / structure 0111111111... 9223372036854775807
const MIN = int(^MAX)          / / structure 10000000... - 9223372036854775808.
func main(a) {
    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
    ifmin ! = MAX { ans++ } dp[t] = ansreturn ans
}
func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}
Copy the code

The result is as follows:

Left god Java code

comments