Leetcode 1255:得分最高的单词集合(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1255:得分最高的单词集合(超详细的解法!!!)

in leetcode with 0 comment

你将会得到一份单词表 words,一个字母表 letters (可能会有重复字母),以及每个字母对应的得分情况表 score

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」:能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中,分数最高的单词集合的得分。

单词拼写游戏的规则概述如下:

示例 1:

输入:words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出:23
解释:
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters,我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5),得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2:

输入:words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出:27
解释:
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters,我们可以组成单词 "ax" (4+5), "bx" (4+5) 和 "cx" (4+5) ,总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3:

输入:words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出:0
解释:
字母 "e" 在字母表 letters 中只出现了一次,所以无法组成单词表 words 中的单词。

提示:

解题思路

由于数据量很小,所以这个题目直接dfs就可以过。参考Leetcode 78:子集(最详细的解法!!!),将所有符合条件的单词计算它们的子集,然后取所有子集中最大得分的那个即可。

首先需要统计每个单词的得分,可以使用collections.Counter统计字母出现次数,然后再计分。collections.Counter可以进行集合运算,所以通过判断letters中字母的集合是不是包含每个单词中字母的集合(先计算差集,再判断差集是不是单词字母构成的集合即可)。

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        data, lc  = [], collections.Counter(letters)
        for w in words:
            wc = collections.Counter(w)
            data.append([wc, sum(j * score[(ord(i) - 97)] for i, j in wc.items())])
        
        def dfs(i, t):
            if not t or i == len(data):
                return 0
            res = max(0, dfs(i + 1, t))
            dif  = t - data[i][0]
            if (t == data[i][0]) or (dif and dif + data[i][0] == t):
                res = max(res, dfs(i + 1, t - data[i][0]) + data[i][1])
            return res

        return dfs(0, lc)

当然也可以不使用collections.Counter,手动去实现统计功能也可以。

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        n = len(words)
        cnt = [0] * 26
        for c in letters:
            cnt[ord(c) - 97] += 1
            
        def dfs(i):
            if i == n:
                return 0
            res = max(0, dfs(i + 1))
            tmp, val = 0, True
            for c in words[i]:
                t = ord(c) - 97
                cnt[t] -= 1
                tmp += score[t]
                if cnt[t] < 0:
                    val = False
            if val:
                res = max(res, dfs(i + 1) + tmp)
            for c in words[i]:
                cnt[ord(c) - 97] += 1
            return res
        return dfs(0)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses