Kimi2.5LeetCode 1255.得分最高的单词集合 public int maxScoreWords(String[] words, char[] letters, int[] score)

我来帮你解决 LeetCode 1255. 得分最高的单词集合 这道题目。题目分析这是一道经典的状态压缩动态规划问题。我们需要从words中选择一些单词使得每个字母的使用次数不超过letters中该字母的数量得分最高解题思路统计可用字母先统计letters中每个字母的数量预处理每个单词计算每个单词需要的字母数量以及该单词的得分状态压缩DP用二进制表示选择了哪些单词枚举所有可能的子集代码实现publicintmaxScoreWords(String[]words,char[]letters,int[]score){intnwords.length;// 统计可用字母数量 (a-z 对应 0-25)int[]availablenewint[26];for(charc:letters){available[c-a];}intmaxScore0;// 枚举所有可能的单词组合用二进制位表示// 第 i 位为 1 表示选择 words[i]for(intmask0;mask(1n);mask){int[]usednewint[26];// 当前组合使用的字母数量inttotalScore0;booleanvalidtrue;// 遍历所有被选中的单词for(inti0;in;i){if((mask(1i))0)continue;// 第 i 个单词未被选中Stringwordwords[i];// 计算该单词的得分和字母使用for(charc:word.toCharArray()){intidxc-a;used[idx];totalScorescore[idx];// 如果超过可用数量该组合无效if(used[idx]available[idx]){validfalse;break;}}if(!valid)break;}if(valid){maxScoreMath.max(maxScore,totalScore);}}returnmaxScore;}复杂度分析维度 复杂度 说明时间复杂度 O(2ⁿ × L) n 为单词数L 为单词平均长度空间复杂度 O(1) 只使用了常数额外空间优化版本预处理如果单词数较多可以先预处理每个单词的信息publicintmaxScoreWords(String[]words,char[]letters,int[]score){intnwords.length;// 预处理每个单词的字母计数和得分int[][]wordCountnewint[n][26];int[]wordScorenewint[n];for(inti0;in;i){for(charc:words[i].toCharArray()){wordCount[i][c-a];wordScore[i]score[c-a];}}// 统计可用字母int[]availablenewint[26];for(charc:letters){available[c-a];}intmaxScore0;// 状态压缩DPfor(intmask0;mask(1n);mask){int[]usednewint[26];inttotalScore0;booleanvalidtrue;for(inti0;in;i){if((mask(1i))0)continue;// 快速检查该单词是否可用for(intj0;j26;j){used[j]wordCount[i][j];if(used[j]available[j]){validfalse;break;}}if(!valid)break;totalScorewordScore[i];}if(valid){maxScoreMath.max(maxScore,totalScore);}}returnmaxScore;}示例验证输入: 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 (51511) 和 good (322512)总共 23 分这个解法利用了状态压缩枚举所有子集是处理从 n 个元素中选若干个子集类问题的经典方法。