LeetCode 1255. 得分最高的单词集合
字数 2752 2025-12-10 18:24:43

LeetCode 1255. 得分最高的单词集合

题目描述
你被给定一个单词列表 words、一个字符列表 letters（每个字符是一个小写字母）以及一个长度数组 score，其中 score[0] 到 score[25] 分别对应字母 'a' 到 'z' 的分数。
你需要从 letters 中选出一些字符（每个字符最多用一次）来拼出 words 中的单词（每个单词可以拼一次或不拼）。拼出一个单词时，你需要使用 letters 中的字符，且每个字符只能在一个单词中使用一次（即被选用的字符总数不能超过 letters 中字符的总数）。
你的目标是选择一些单词（可以是一个子集）来拼写，使得这些单词的得分总和最大，并返回这个最大得分。
如果无法拼出任何单词，则返回 0。

示例
输入：
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
解释：
可以拼出单词 "dad"（得分 5+1+5=11）和 "good"（得分 3+2+2+5=12），总分为 23。

解题思路与步骤详解

1. 问题分析

  • 我们需要从 words 中选出一个子集（可以包括所有单词或不选）。
  • 对于选中的每个单词，需要用 letters 中的字符来拼写。
  • 每个字符最多用一次（跨所有选中的单词总使用次数不能超过它在 letters 中的出现次数）。
  • 每个单词可以被拼写一次或不拼（不能重复拼同一个单词多次）。
  • 单词的得分是其所有字母对应分数之和。
  • 目标是最大化总得分。

2. 数据预处理

我们先将 letters 转换为一个长度为 26 的整数数组 letterCount，记录每个字母可用的数量。
例如，letters = ["a","a","c"] 转换为 letterCount[0]=2（两个 'a'），letterCount[2]=1（一个 'c'），其余为 0。

同时，为了方便后续计算，我们预先计算每个单词的得分以及它需要的字母数量（一个长度为 26 的数组 wordNeed[i][j]，表示第 i 个单词需要字母 j 的数量）。

3. 搜索策略选择

这是一个典型的“子集选择”问题，每个单词可以选或不选，但选择受到字母资源限制。
由于 words 的长度最多为 14（题目约束），因此我们可以使用状态压缩来枚举所有单词子集（共 2^n 种可能，n ≤ 14，最多 16384 种），对每一种子集检查是否能用 letters 中的字符拼出这些单词，并计算总得分。

4. 状态压缩枚举

用二进制数 mask 表示一个子集，其中第 i 位为 1 表示选择 words[i]。
我们遍历所有 mask（从 0 到 (1<<n)-1），对每个 mask：

  • 初始化一个长度为 26 的数组 used 记录该子集总共需要的每个字母的数量。
  • 遍历 mask 中为 1 的每一位，将对应单词的字母需求加到 used 中。
  • 检查是否满足：对于每个字母 c，used[c] <= letterCount[c]。
  • 如果满足，计算这个子集的总得分（可以累加每个选中单词的得分）。
  • 更新最大得分。

5. 计算单词得分和需求

为了高效，我们提前计算好：

  • wordScore[i]：单词 words[i] 的得分。
  • wordCharCount[i][c]：单词 words[i] 需要字母 c 的数量。

这样在枚举时，只需累加 wordScore 和 wordCharCount，避免重复计算。

6. 算法步骤总结

  1. 统计 letters 中每个字母的出现次数，存入 letterCount[26]。
  2. 对每个单词 words[i]：
    • 计算其得分 wordScore[i]（累加每个字母的 score[ch-'a']）。
    • 统计其字母需求 wordCharCount[i][26]（每个字母出现次数）。
  3. 枚举所有 mask 从 0 到 (1<<n)-1：
    • 初始化 used[26] = {0}。
    • 对每个在 mask 中为 1 的位 i：
      • 对每个字母 c，used[c] += wordCharCount[i][c]。
    • 检查是否所有 used[c] <= letterCount[c]。
    • 如果是，计算总得分 totalScore = sum(wordScore[i] for i in mask)。
    • 更新最大得分 maxScore = max(maxScore, totalScore)。
  4. 返回 maxScore。

7. 复杂度分析

  • 单词数 n ≤ 14，枚举子集数 O(2^n) ≤ 16384。
  • 每个子集检查时，需要遍历所有选中的单词（最多 n 个），每个单词检查 26 个字母，因此每个子集检查为 O(26n)。
  • 总时间复杂度 O(2^n * 26n)，在 n=14 时约为 16384 * 364 ≈ 6e6，可以接受。
  • 空间复杂度 O(26n) 用于存储单词的字母需求。

8. 举例验证

以示例为例：

  • letterCount: a:2, c:1, d:3, g:1, o:2，其余为 0。
  • 单词需求：
    • "dog": d:1, o:1, g:1
    • "cat": c:1, a:1, t:1
    • "dad": d:2, a:1
    • "good": g:1, o:2, d:1
  • 单词得分（根据 score 数组计算）：
    • "dog": d(5)+o(2)+g(3)=10
    • "cat": c(9)+a(1)+t(0)=10
    • "dad": d(5)+a(1)+d(5)=11
    • "good": g(3)+o(2)+o(2)+d(5)=12
  • 枚举所有子集：
    • 选择 {"dad","good"}（子集掩码对应这两个单词）：
      • 需求：d:3, a:1, g:1, o:2。
      • 与 letterCount 比较：满足（d:3≤3, a:1≤2, g:1≤1, o:2≤2）。
      • 得分：11+12=23，为最大。

因此算法输出 23，与示例一致。

这个算法通过状态压缩枚举所有可能的单词子集，并检查资源限制，从而找到最优解。由于单词数量较少，枚举是可行的。

LeetCode 1255. 得分最高的单词集合 题目描述 你被给定一个单词列表 words 、一个字符列表 letters （每个字符是一个小写字母）以及一个长度数组 score ，其中 score[0] 到 score[25] 分别对应字母 'a' 到 'z' 的分数。 你需要从 letters 中选出一些字符（每个字符最多用一次）来拼出 words 中的单词（每个单词可以拼一次或不拼）。拼出一个单词时，你需要使用 letters 中的字符，且每个字符只能在一个单词中使用一次（即被选用的字符总数不能超过 letters 中字符的总数）。 你的目标是选择一些单词（可以是一个子集）来拼写，使得这些单词的得分总和最大，并返回这个最大得分。 如果无法拼出任何单词，则返回 0 。 示例 输入： 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 解释： 可以拼出单词 "dad"（得分 5+1+5=11）和 "good"（得分 3+2+2+5=12），总分为 23。 解题思路与步骤详解 1. 问题分析 我们需要从 words 中选出一个子集（可以包括所有单词或不选）。 对于选中的每个单词，需要用 letters 中的字符来拼写。 每个字符最多用一次（跨所有选中的单词总使用次数不能超过它在 letters 中的出现次数）。 每个单词可以被拼写一次或不拼（不能重复拼同一个单词多次）。 单词的得分是其所有字母对应分数之和。 目标是最大化总得分。 2. 数据预处理 我们先将 letters 转换为一个长度为 26 的整数数组 letterCount ，记录每个字母可用的数量。 例如， letters = ["a","a","c"] 转换为 letterCount[0]=2 （两个 'a'）， letterCount[2]=1 （一个 'c'），其余为 0。 同时，为了方便后续计算，我们预先计算每个单词的得分以及它需要的字母数量（一个长度为 26 的数组 wordNeed[i][j] ，表示第 i 个单词需要字母 j 的数量）。 3. 搜索策略选择 这是一个典型的“子集选择”问题，每个单词可以选或不选，但选择受到字母资源限制。 由于 words 的长度最多为 14（题目约束），因此我们可以使用 状态压缩 来枚举所有单词子集（共 2^n 种可能，n ≤ 14，最多 16384 种），对每一种子集检查是否能用 letters 中的字符拼出这些单词，并计算总得分。 4. 状态压缩枚举 用二进制数 mask 表示一个子集，其中第 i 位为 1 表示选择 words[i] 。 我们遍历所有 mask （从 0 到 (1<<n)-1 ），对每个 mask ： 初始化一个长度为 26 的数组 used 记录该子集总共需要的每个字母的数量。 遍历 mask 中为 1 的每一位，将对应单词的字母需求加到 used 中。 检查是否满足：对于每个字母 c ， used[c] <= letterCount[c] 。 如果满足，计算这个子集的总得分（可以累加每个选中单词的得分）。 更新最大得分。 5. 计算单词得分和需求 为了高效，我们提前计算好： wordScore[i] ：单词 words[i] 的得分。 wordCharCount[i][c] ：单词 words[i] 需要字母 c 的数量。 这样在枚举时，只需累加 wordScore 和 wordCharCount ，避免重复计算。 6. 算法步骤总结 统计 letters 中每个字母的出现次数，存入 letterCount[26] 。 对每个单词 words[i] ： 计算其得分 wordScore[i] （累加每个字母的 score[ch-'a'] ）。 统计其字母需求 wordCharCount[i][26] （每个字母出现次数）。 枚举所有 mask 从 0 到 (1<<n)-1 ： 初始化 used[26] = {0} 。 对每个在 mask 中为 1 的位 i ： 对每个字母 c ， used[c] += wordCharCount[i][c] 。 检查是否所有 used[c] <= letterCount[c] 。 如果是，计算总得分 totalScore = sum(wordScore[i] for i in mask) 。 更新最大得分 maxScore = max(maxScore, totalScore) 。 返回 maxScore 。 7. 复杂度分析 单词数 n ≤ 14，枚举子集数 O(2^n) ≤ 16384。 每个子集检查时，需要遍历所有选中的单词（最多 n 个），每个单词检查 26 个字母，因此每个子集检查为 O(26n)。 总时间复杂度 O(2^n * 26n)，在 n=14 时约为 16384 * 364 ≈ 6e6，可以接受。 空间复杂度 O(26n) 用于存储单词的字母需求。 8. 举例验证 以示例为例： letterCount: a:2, c:1, d:3, g:1, o:2 ，其余为 0。 单词需求： "dog": d:1, o:1, g:1 "cat": c:1, a:1, t:1 "dad": d:2, a:1 "good": g:1, o:2, d:1 单词得分（根据 score 数组计算）： "dog": d(5)+o(2)+g(3)=10 "cat": c(9)+a(1)+t(0)=10 "dad": d(5)+a(1)+d(5)=11 "good": g(3)+o(2)+o(2)+d(5)=12 枚举所有子集： 选择 {"dad","good"}（子集掩码对应这两个单词）： 需求：d:3, a:1, g:1, o:2。 与 letterCount 比较：满足（d:3≤3, a:1≤2, g:1≤1, o:2≤2）。 得分：11+12=23，为最大。 因此算法输出 23，与示例一致。 这个算法通过状态压缩枚举所有可能的单词子集，并检查资源限制，从而找到最优解。由于单词数量较少，枚举是可行的。