# 1255. 得分最高的单词集合
### 题目地址（1255. 得分最高的单词集合）
### 题目描述
```
你将会得到一份单词表 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] 只包含小写的英文字母。
```
### 前置知识
* 回溯
### 公司
* 暂无
### 思路
题目的本质就是枚举所有的 words 组合，然后判断是否可以满足单词拼写的游戏规则，最后找出所有满足条件的最大分数即可。因此这道题可以用到 [78. 子集](/leetcode-solution/medium/78.subsets.md) 的代码。
由排列组合原理可知， 一个大小为 N 的集合的组合数是 2^N，因此这种解法的时间复杂度也大致是这个量级。
这道题比[78. 子集](/leetcode-solution/medium/78.subsets.md) 稍微复杂一点，不管是题目的数据输入还是限制条件都更复杂。
实际上， 这些限制条件影响的只是部分细节，我们仍然套用回溯的模板即可， 关于回溯模板可参考：[回溯专题](/leetcode-solution/thinkings/backtrack.md)。
核心伪代码如下：
```py
class Solution:
def maxScoreWords(self, words, letters, score):
ans = 0
def dfs(start, 当前的分数, counter):
if start > len(words): return
ans = max(ans, cur)
for j in 循环start之后的单词:
if 如果当前单词加进去还满足游戏规则:
dfs(j + 1, 新的分数, 新的counter)
dfs(0, 0, collections.Counter(letters))
return ans
```
> 由于每次都新生成一个 counter，因此状态不需要回溯。
其中 collections.Counter(letters) 的功能是计数，比如\['a', 'a', 'c', 'b']，会被处理为 { a: 2, b: 1, c: 1}。其功能是用于判断**当前单词加进去是否还满足游戏规则**。具体可以参考下方的代码区。
### 关键点
* 回溯模板
* 计数
### 代码
代码支持 Python3:
Python3 Code:
```python
class Solution:
def maxScoreWords(self, words, letters, score):
self.ans = 0
words_score = [sum(score[ord(c)-ord('a')] for c in word) for word in words]
words_counter = [collections.Counter(word) for word in words]
def backtrack(start, cur, counter):
if start > len(words):
return
self.ans = max(self.ans, cur)
for j, w_counter in enumerate(words_counter[start:], start):
if all(n <= counter.get(c,0) for c,n in w_counter.items()):
backtrack(j+1, cur+words_score[j], counter-w_counter)
backtrack(0, 0, collections.Counter(letters))
return self.ans
```
**复杂度分析**
* 时间复杂度：$O(2^N)$，其中 N 为 words 的个数。
* 空间复杂度：$O(total)$，其中 total 为 words 中的字符总数。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1255.maximum-score-words-formed-by-letters.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.