Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

把這幾天寫的每日，整理一下騙個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']--
                                cnt += score[words[i][j]-'a']
                                if tmp[words[i][j]-'a'] < 0 {
                                        enough = false
                                        break
                                }
                        }
                        if enough {
                                dfs(i+1, tmp, sum+cnt)
                        } else {
                                dfs(i+1, rec, sum)
                        }
                }
        }
        dfs(0, freq, 0)
        return res
}

--
https://i.imgur.com/r9FBAGO.gif

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.164.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716610360.A.1AD.html
→ oin1104: zzz