golang力扣leetcode 691.贴纸拼词

1.既然可用重复拿取，说明只遍历一次数组是不够的
2.第一次用元素拼凑，可能不够，还要第二次，第二次需要的数量，与第一次拼凑之后的状态有关
3.对于这种当前状态与上一次状态有关的，用BFS来做
1.对target字符串中出现的字母计数，得到一个26长度的数组
2.对stickers字符串数组中每个字符串都计数，得到多个26长度的数组
3.遍历mapTarget，再遍历mapStickers ，用arrTar减去arrSticker得到新的数组状态temp
4.这个新的状态temp，是目标字符串减去某个字符串之后的状态，对于这个状态，就是下一轮的目标了
5.如果数组都是0，也就是等于zero ，说明拼凑成功了，直接返回
6.如果不是0，并且temp不在mapTarget中，则加入下一轮bfs中

func minStickers(stickers []string, target string) (ans int) {
  mapTarget := make(map[[26]int]bool)   //存目标
  mapStickers := make(map[[26]int]bool) //存待使用
  mapTemp := make(map[[26]int]bool)     //存下一次目标
  zero := [26]int{}
  tar := [26]int{} //将target的字母出现次数计数到数组中
  for i := 0; i < len(target); i++ {
    tar[int(target[i]-97)]++
  }
  mapTarget[tar] = true
  for _, sticker := range stickers {
    temp := [26]int{}
    for i := 0; i < len(sticker); i++ {
      temp[int(sticker[i]-97)]++ //将sticker的字母出现次数计数到数组中
    }
    mapStickers[temp] = true
  }
  for len(mapTarget) != 0 {
    ans++
    for arrTar := range mapTarget {
      for arrSticker := range mapStickers {
        temp := [26]int{}
        for i := 0; i < 26; i++ {
          if arrTar[i]-arrSticker[i] >= 0 {
            temp[i] = arrTar[i] - arrSticker[i]
          }
        }
        if temp == zero {
          return ans
        } else if !mapTarget[temp] { //如果map中有过temp，则不用再存了，没有才存
          mapTemp[temp] = true
        }
      }
    }
    mapTarget = mapTemp //将待使用转正
    mapTemp = make(map[[26]int]bool)
  }
  return -1
}