leetcode-go/leetcode/hard/691.stickers-to-spell-word.go

func minStickers(stickers []string, target string) int {
	n := len(stickers)
	options := make([][26]int, n)
	goal := [26]int{}
	set1, set2 := cntFreq(target, goal[:]), 0
	for i, s := range stickers {
		set2 |= cntFreq(s, options[i][:])
	}
	for mask := 1; mask < 1<<26; mask <<= 1 {
		if mask&set1 != 0 && mask&set2 == 0 {
			return -1
		}
	}
	dp := make(map[[26]int]int)
	return dfs(options, goal, set1, dp)
}

func dfs(options [][26]int, goal [26]int, set int, dp map[[26]int]int) int {
	if v, ok := dp[goal]; ok {
		return v
	} else if set == 0 {
		return 0
	}
	res := math.MaxInt32
	for i := 0; i < len(options); i++ {
		ret, next, nset := sub(goal, options[i])
		if !ret {
			continue
		}
		if val := dfs(options, next, nset, dp) + 1; val < res {
			res = val
		}
	}
	dp[goal] = res
	return res
}

func sub(a, b [26]int) (flag bool, res [26]int, set int) {
	for i := 0; i < 26; i++ {
		if det := a[i] - b[i]; 0 < det {
			res[i] = det
			set |= 1 << uint(i)
		}
		if a[i] != 0 && b[i] != 0 {
			flag = true
		}
	}
	return
}

func cntFreq(word string, freq []int) (set int) {
	for _, r := range word {
		i := r - 'a'
		freq[i]++
		set |= 1 << uint(i)
	}
	return
}