1. 題目

你將會得到一份單詞表 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] 只包含小寫的英文字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-score-words-formed-by-letters
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 看數據量不是很大，直接回溯，枚舉所有可能（每個單詞取或者不取，2¹⁴=16384）

class Solution {int maxscore = 0; public:int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {int n = words.size(), i;vector<int> count(26,0);for(i = 0; i < letters.size(); ++i)count[letters[i]-'a']++;//可使用的字母數量dfs(words, count, score, 0, 0);return maxscore;}void dfs(vector<string>& words, vector<int>& count, vector<int>& score, int i, int sc){if(i == words.size()){if(canAdd(count))//所選單詞組合滿足條件maxscore = max(maxscore, sc);return;}//加入該單詞for(int j = 0; j < words[i].size(); ++j){ //更新單詞得分，計數減少sc += score[words[i][j]-'a'];count[words[i][j]-'a']--;}dfs(words, count, score, i+1, sc);for(int j = 0; j < words[i].size(); ++j){ //回溯，計數重置，得分減去sc -= score[words[i][j]-'a'];count[words[i][j]-'a']++;}//不加入該單詞dfs(words, count, score, i+1, sc);}bool canAdd(vector<int>& count){for(int i = 0; i < 26; ++i){if(count[i] < 0)return false;}return true;} };

32 ms 8.7 MB

總結

以上是生活随笔為你收集整理的LeetCode 1255. 得分最高的单词集合（回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。