LEETCODE 1255. Maximum Score Words Formed by Letters 解题思路分析

题目大意:

得分最高的单词集合

你将会得到一份单词表 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数组中存在足够多的字符能够拼出当前单词,那么我们就要做出选择,是拼当前字符还是不拼,这两种选择哪种会导致全局结果更好,当前是无法得知的,因此要递归到子问题中继续求解。

解题步骤大概如下:

  1. 先统计下letters数组中26个小写字母各有多少个。
  2. 从words数组中第一个index的字符串开始递归,如果letters数组中没有足够多的字符能够组成当前字符串,index加一递归到下一层。
  3. 反之,我们有两种选择,第一,将当前字符拼写出来,同时在letters数组中减去使用掉的字符数量,再算出当前字符串能够得到的积分,最后index加一递归到下一层。第二中选择是,我们不拼写当前字符串,直接index加一递归到下一层。比较两种选择结果更好的一方返回。
  4. 递归结束条件为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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1255-maximum-score-words-formed-by-letters-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。