题目大意：
得分最高的单词集合
你将会得到一份单词表 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] 只包含小写的英文字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1255
解题思路分析：
又是一道递归思想的题目，最近这个类型的题目做的比较多，所以看了题目之后马上就想出了解题思路。
先看words数组中的单词能不能被拼写出来，这取决于letters数组中有没有相应足够多的字符，如果没有肯定是要被pass掉的，关键在于，如果letters数组中存在足够多的字符能够拼出当前单词，那么我们就要做出选择，是拼当前字符还是不拼，这两种选择哪种会导致全局结果更好，当前是无法得知的，因此要递归到子问题中继续求解。
解题步骤大概如下：
- 先统计下letters数组中26个小写字母各有多少个。
- 从words数组中第一个index的字符串开始递归，如果letters数组中没有足够多的字符能够组成当前字符串，index加一递归到下一层。
- 反之，我们有两种选择，第一，将当前字符拼写出来，同时在letters数组中减去使用掉的字符数量，再算出当前字符串能够得到的积分，最后index加一递归到下一层。第二中选择是，我们不拼写当前字符串，直接index加一递归到下一层。比较两种选择结果更好的一方返回。
- 递归结束条件为index到达words数组末尾。
这是一个标准的递归思路，看下完整实现代码：
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int[] letterCount = new int[26]; // 用来统计每个字符的个数
// 统计每个字符的个数
for(char c : letters) letterCount[c-'a']++;
// 从第一个字符串开始递归
return helper(words, letterCount, score, 0, 0);
}
// words：words数组
// letterCount：letters数组中每种字符的个数
// score：score数组
// sum：当前为止的累计得分
// index：当前index
int helper(String[] words, int[] letterCount, int[] score, int sum, int index){
// 如果index达到数组末尾，递归结束，返回当前累计得分
if(index == words.length) return sum;
String word=words[index]; // 当前字符串
int res = 0; // 返回结果（累计得分）
// 如果存在足够的字符能够组成当前字符串
if(hasWord(word, letterCount)){
// 第一种选择：拼写出当前字符串
int s=0; // 当前字符串能够拿到的分数
// 循环字符串中每个字符
for(int i=0;i<word.length();i++){
// 消耗一个当前字符
letterCount[word.charAt(i)-'a']--;
// 累加分数
s+=score[word.charAt(i)-'a'];
}
// sum加上当前字符串分数，index加一，递归到下一层
res = helper(words, letterCount, score, sum+s, index+1);
// 递归后将letterCount数组个数还原
for(int i=0;i<word.length();i++){
letterCount[word.charAt(i)-'a']++;
}
}
// 第二种选择：不拼写出当前字符串，即直接index加一递归到下一层
// 返回两种选择的最大值
return Math.max(res, helper(words, letterCount, score, sum, index+1));
}
// 查看letterCount中是否含有足够的字符以能够组成字符串word
boolean hasWord(String word, int[] letterCount){
int[] count = new int[26];
for(int i=0;i<word.length();i++){
count[word.charAt(i)-'a']++;
}
for(int i=0;i<26;i++){
if(count[i]>letterCount[i]){
return false;
}
}
return true;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 98.92% of Java online submissions for Maximum Score Words Formed by Letters.
Memory Usage: 38 MB, less than 100.00% of Java online submissions for Maximum Score Words Formed by Letters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1255-maximum-score-words-formed-by-letters-解题思路分析/