Hard

题目描述

给你一份单词表 words，一份字母表 letters（可能重复），以及每个字母的得分表 score。

返回由给定字母组成的任意有效单词集合的最大得分（words[i] 不能使用两次或更多次）。

不必使用字母表中的所有字符，每个字母只能使用一次。字母 '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
给定字母，我们可以组成单词 "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
给定字母，我们可以组成单词 "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" 只能使用一次。

提示：

  • 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] 仅包含小写英文字母

解题思路

这是一道典型的子集枚举问题。由于单词数量最多14个，我们可以枚举所有可能的单词组合（2^14 = 16384种），对每种组合检查是否可行并计算得分。

解题思路：

  1. 位掩码枚举：使用二进制位掩码表示选择的单词组合，遍历所有可能的子集
  2. 字母计数：统计可用字母的数量，对于每个组合，检查是否有足够的字母组成所选单词
  3. 得分计算：如果字母足够，计算该组合的总得分并更新最大值

算法步骤：

  1. 统计可用字母的数量
  2. 遍历所有可能的单词组合（使用位掩码从0到2^n-1）
  3. 对每个组合：
    • 统计所需字母数量
    • 检查是否超过可用字母数量
    • 如果可行，计算得分并更新最大值
  4. 返回最大得分

时间复杂度为O(2^n × m)，其中n是单词数量，m是单词平均长度。由于n≤14，这个复杂度是可接受的。

代码实现

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> letterCount(26, 0);
        for (char c : letters) {
            letterCount[c - 'a']++;
        }
        
        int n = words.size();
        int maxScore = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> usedCount(26, 0);
            int currentScore = 0;
            bool valid = true;
            
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    for (char c : words[i]) {
                        usedCount[c - 'a']++;
                        currentScore += score[c - 'a'];
                    }
                }
            }
            
            for (int i = 0; i < 26; i++) {
                if (usedCount[i] > letterCount[i]) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                maxScore = max(maxScore, currentScore);
            }
        }
        
        return maxScore;
    }
};

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        from collections import Counter
        
        letter_count = Counter(letters)
        n = len(words)
        max_score = 0
        
        for mask in range(1 << n):
            used_count = Counter()
            current_score = 0
            
            for i in range(n):
                if mask & (1 << i):
                    for c in words[i]:
                        used_count[c] += 1
                        current_score += score[ord(c) - ord('a')]
            
            valid = True
            for char, count in used_count.items():
                if count > letter_count[char]:
                    valid = False
                    break
            
            if valid:
                max_score = max(max_score, current_score)
        
        return max_score

public class Solution {
    public int MaxScoreWords(string[] words, char[] letters, int[] score) {
        int[] letterCount = new int[26];
        foreach (char c in letters) {
            letterCount[c - 'a']++;
        }
        
        int n = words.Length;
        int maxScore = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int[] usedCount = new int[26];
            int currentScore = 0;
            bool valid = true;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    foreach (char c in words[i]) {
                        usedCount[c - 'a']++;
                        currentScore += score[c - 'a'];
                    }
                }
            }
            
            for (int i = 0; i < 26; i++) {
                if (usedCount[i] > letterCount[i]) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                maxScore = Math.Max(maxScore, currentScore);
            }
        }
        
        return maxScore;
    }
}

var maxScoreWords = function(words, letters, score) {
    const letterCount = new Array(26).fill(0);
    for (const c of letters) {
        letterCount[c.charCodeAt(0) - 97]++;
    }
    
    const n = words.length;
    let maxScore = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        const usedCount = new Array(26).fill(0);
        let currentScore = 0;
        let valid = true;
        
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (const c of words[i]) {
                    const idx = c.charCodeAt(0) - 97;
                    usedCount[idx]++;
                    currentScore += score[idx];
                }
            }
        }
        
        for (let i = 0; i < 26; i++) {
            if (usedCount[i] > letterCount[i]) {
                valid = false;
                break;
            }
        }
        
        if (valid) {
            maxScore = Math.max(maxScore, currentScore);
        }
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(2^n × m)，其中n是单词数量（≤14），m是所有单词的总字符数
空间复杂度O(1)，只使用了固定大小的数组来统计字母数量

相关题目