得分最高的单词集合

难度: Hard

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

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

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

玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 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 中的单词。

提示：

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i] 和 letters[i] 只包含小写的英文字母。

Submission

运行时间: 32 ms

内存: 16.4 MB

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        class State():
            def __init__(o):
                #记录每个字母还可以使用的次数
                o.total_score: int = 0
                o.max_score: int = 0
                o.counter: Dict[str,int] = dict(Counter(letters))
                o.LOG: List[int] = [] #记录选择的所有单词
                o.counter_for_each_word: List[List[Tuple[str,int]]] = []
                o.score_for_each_word: List[int] = []
                for w in words:
                    s: int = 0
                    cnt = Counter(w)
                    L: int = 0
                    for c,n in cnt.items():
                        if c not in o.counter or n>o.counter[c]:break
                        L += n
                        s += score[ord(c)-ord('a')]*n
                    if L<len(w): continue
                    o.counter_for_each_word.append(cnt.items())
                    o.score_for_each_word.append(s)
                print(o.score_for_each_word)
                o.N: int = len(o.score_for_each_word)

            #选择拼写word[i]
            def exec(o, i: int):
                #print(i)
                for c,n in o.counter_for_each_word[i]:
                    if o.counter[c]<n:
                        return True
                    o.counter[c] -= n
                o.total_score += o.score_for_each_word[i]
                #print(i, o.total_score)
                if o.total_score>o.max_score:
                    o.max_score = o.total_score
                    #print(o.max_score)
                return False

        state: State = State()   
        def backtrace(foo):
            def inner(i: int):
                counter_items = [(c,n) for c,n in state.counter.items()]
                #print(i, counter_items)
                total_score = state.total_score
                ans = foo(i)
                #print(i, state.total_score)
                state.total_score = total_score
                for c,n in counter_items: state.counter[c] = n
                return ans
            return inner

        @backtrace
        def dfs(i: int):
            if state.exec(i):
                return
            for j in range(i+1, state.N):
                dfs(j)
                
        for i in range(state.N):
            dfs(i)
        return state.max_score

Explain

这个题解采用了回溯搜索的方法来求解最高得分。具体思路如下： 1. 首先预处理每个单词的得分以及需要的字母数量，过滤掉无法拼写的单词。 2. 然后使用回溯搜索，从第一个单词开始，依次尝试选择每个单词。 3. 对于每个选择的单词，先判断当前剩余字母是否足够拼写该单词，如果不够则跳过。 4. 如果足够，则减去相应的字母数量，并将该单词的得分加到总得分中。 5. 继续递归搜索下一个单词，直到所有单词都尝试完毕。 6. 搜索过程中记录最大的总得分，作为最终结果返回。

时间复杂度: O(L*2^N)

空间复杂度: O(NL + M)

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        class State():
            def __init__(o):
                #记录每个字母还可以使用的次数
                o.total_score: int = 0
                o.max_score: int = 0
                o.counter: Dict[str,int] = dict(Counter(letters))
                o.LOG: List[int] = [] #记录选择的所有单词
                o.counter_for_each_word: List[List[Tuple[str,int]]] = []
                o.score_for_each_word: List[int] = []
                for w in words:
                    s: int = 0
                    cnt = Counter(w)
                    L: int = 0
                    for c,n in cnt.items():
                        if c not in o.counter or n>o.counter[c]:break
                        L += n
                        s += score[ord(c)-ord('a')]*n
                    if L<len(w): continue
                    o.counter_for_each_word.append(cnt.items())
                    o.score_for_each_word.append(s)
                print(o.score_for_each_word)
                o.N: int = len(o.score_for_each_word)

            #选择拼写word[i]
            def exec(o, i: int):
                #print(i)
                for c,n in o.counter_for_each_word[i]:
                    if o.counter[c]<n:
                        return True
                    o.counter[c] -= n
                o.total_score += o.score_for_each_word[i]
                #print(i, o.total_score)
                if o.total_score>o.max_score:
                    o.max_score = o.total_score
                    #print(o.max_score)
                return False

        state: State = State()   
        def backtrace(foo):
            def inner(i: int):
                counter_items = [(c,n) for c,n in state.counter.items()]
                #print(i, counter_items)
                total_score = state.total_score
                ans = foo(i)
                #print(i, state.total_score)
                state.total_score = total_score
                for c,n in counter_items: state.counter[c] = n
                return ans
            return inner

        @backtrace
        def dfs(i: int):
            if state.exec(i):
                return
            for j in range(i+1, state.N):
                dfs(j)
                
        for i in range(state.N):
            dfs(i)
        return state.max_score

Explore

在预处理阶段，决定一个单词是否可以被拼写出来的依据确实是通过比较字母的计数。具体来说，我首先统计了字母表中每个字母的可用次数，然后对于每个单词，计算它所需的每个字母的数量。如果单词中任何一个字母所需的数量超过了该字母的可用数量，则认为这个单词无法被完整地拼写出来，因此不考虑这个单词。这样可以有效地减少搜索空间，提高算法效率。

在回溯过程中，选择`如果剩余字母不足以拼写单词则跳过`的原因是基于单词的完整性。在本题中，单词的得分是基于完整单词的，不完整的单词没有得分意义。此外，尝试拼写单词的部分不仅无法获得完整的得分，而且会消耗有限的字母资源，这可能会阻碍后续可能的更高得分单词的拼写。因此，只有当字母充足以拼写整个单词时，才进行选择，这样可以确保每次选择都是有效的，从而最大化总得分。

选择存储每个单词的字母计数的元组列表`cnt.items()`而不是整个Counter对象的原因是为了内存效率和处理速度。使用元组列表可以直接访问字母和它们的计数，而不需要整个Counter对象的额外结构和内存开销。此外，元组列表在回溯和字母数量调整过程中提供了更快的访问和更新速度。这种存储方式简化了数据结构，使得代码更加高效和易于管理。

在回溯搜索过程中，确保每次递归调用都正确地恢复剩余字母的数量和当前的总得分是通过使用装饰器`backtrace`来管理状态恢复。在每次递归前，我记录当前的剩余字母数量和总得分。然后进行递归调用。递归调用后，我使用之前保存的状态将剩余字母的数量和总得分恢复到递归调用前的状态。这样可以确保每次递归调用之后，状态都被正确地恢复，不会互相影响，从而保证了回溯算法的正确执行。