Re: [闲聊] 每日leetcode

楼主: JIWP (JIWP)   2024-05-25 12:12:38
把这几天写的每日,整理一下骗个p币
1255. Maximum Score Words Formed by Letters
给一个words的清单
一组letter和每个字母的对应分数
用letter组合出words中的单字
请找出分数最大的组合
思路:
用freq计算纪录letter中每个字母出现的次数
用backtracking从words的第一个单字开始计算
从freq扣掉words[i]需要的字母,如果字母够那就可以加上这个单字的分数
如果不行就不要记录这个字母,继续往下一个前进
比较过所有组合后
回传最大的分数
golang code :
func maxScoreWords(words []string, letters []byte, score []int) int {
freq := make([]int, 26)
n := len(words)
res := 0
for _, val := range letters {
freq[val-'a']++
}
var dfs func(i int, rec []int, sum int)
dfs = func(idx int, rec []int, sum int) {
if idx == n {
res = max(res, sum)
return
}
for i := idx; i < n; i++ {
tmp := make([]int, 26)
copy(tmp, rec)
cnt := 0
enough := true
for j := 0; j < len(words[i]); j++ {
tmp[words[i][j]-'a']
作者: oin1104 (是oin的说)   2024-05-25 12:22:00
zzz

Links booklink

Contact Us: admin [ a t ] ucptt.com