本文涉及知識點
回溯
力扣難道：1881
LeetCode1255. 得分最高的單詞集合
你將會得到一份單詞表 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] 只包含小寫的英文字母。
回溯
本題可以狀態壓縮動態規劃解決。本題解用回溯。
n = words.length
回溯的層次leve：n。
同層次的回溯：兩次回溯，word[leve]選擇，不選擇。
回溯的狀態： cnt[26]記錄剩余字符的數量，hasScore記錄已經獲取的分數。
回溯的調用：BackTrack(leve,0)
CanSub(cnt1[26],cnt2[26]) 需要的字符是否夠減。
Sub 減少。
Add 加。
回溯代碼
核心代碼
class Solution {
public:int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {int has[26] = { 0 };for (const auto& ch : letters) {has[ch - 'a']++;}int iRet = 0;std::function<void(int, int)> BackTrack = [&](int leve, int hasScore) {if (words.size() == leve) {iRet = max(iRet, hasScore);return;} int cur[26] = { 0 };Init(cur, words[leve]);if (CanSub(has, cur)) {Sub(has, cur);int curScore = 0;for (int i = 0; i < 26; i++) {curScore += cur[i] * score[i];}BackTrack(leve + 1, hasScore+ curScore);Add(has, cur);}BackTrack(leve + 1, hasScore);};BackTrack(0, 0);return iRet;}void Init(int* s, const string& str) {for (const auto& ch : str) {s[ch - 'a']++;}}bool CanSub(int* s1, int* s2) {for (int i = 0; i < 26; i++) {if (s1[i] < s2[i]) { return false; }}return true;}void Sub(int* s1, int* s2) {for (int i = 0; i < 26; i++) {s1[i] -= s2[i];} }void Add(int* s1, int* s2) {for (int i = 0; i < 26; i++) {s1[i] += s2[i];}}
};
測試用例
class Solution {
public:int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {int has[26] = { 0 };for (const auto& ch : letters) {has[ch - 'a']++;}int iRet = 0;std::function<void(int, int)> BackTrack = [&](int leve, int hasScore) {if (words.size() == leve) {iRet = max(iRet, hasScore);return;} int cur[26] = { 0 };Init(cur, words[leve]);if (CanSub(has, cur)) {Sub(has, cur);int curScore = 0;for (int i = 0; i < 26; i++) {curScore += cur[i] * score[i];}BackTrack(leve + 1, hasScore+ curScore);Add(has, cur);}BackTrack(leve + 1, hasScore);};BackTrack(0, 0);return iRet;}void Init(int* s, const string& str) {for (const auto& ch : str) {s[ch - 'a']++;}}bool CanSub(int* s1, int* s2) {for (int i = 0; i < 26; i++) {if (s1[i] < s2[i]) { return false; }}return true;}void Sub(int* s1, int* s2) {for (int i = 0; i < 26; i++) {s1[i] -= s2[i];} }void Add(int* s1, int* s2) {for (int i = 0; i < 26; i++) {s1[i] += s2[i];}}
};
2023年1月
//通過 x &= (x-1)實現
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}
class Solution {
public:
int maxScoreWords(vector& words, vector& letters, vector& score) {
vector vCharNums(26);
for (const auto& ch : letters)
{
vCharNums[ch - ‘a’]++;
}
vector vScore(words.size());
for (int i = 0; i < words.size(); i++)
{
for (const auto& ch : words[i])
{
vScore[i] += score[ch - ‘a’];
}
}
m_iUseWordMaskNum = 1 << words.size();
m_vMaskCharNums.assign(m_iUseWordMaskNum, vector(26));
//只選擇一個words
for (int i = 0; i < words.size(); i++)
{
auto& v = m_vMaskCharNums[1<<i];
for (const auto& ch : words[i])
{
v[ch - ‘a’]++;
}
}
//多個字符 words
for (int iMask = 1; iMask < m_iUseWordMaskNum; iMask++)
{
if (1 == bitcount(iMask))
{
continue;
}
int iSumMask = (iMask - 1)&iMask;
int iSumMask2 = iMask - iSumMask;
for (int j = 0; j < 26; j++)
{
m_vMaskCharNums[iMask][j] = m_vMaskCharNums[iSumMask][j] + m_vMaskCharNums[iSumMask2][j];
}
}
int iMaxScore = 0;
for (int iMask = 1; iMask < m_iUseWordMaskNum; iMask++)
{
bool bVilid = true;
for (int j = 0; j < 26; j++)
{
if (m_vMaskCharNums[iMask][j] > vCharNums[j])
{
bVilid = false;
break;
}
}
if (bVilid)
{
int iSorce = 0;
for (int i = 0; i < words.size(); i++)
{
if (iMask & (1 << i))
{
iSorce += vScore[i];
}
}
iMaxScore = max(iMaxScore, iSorce);
}
}
return iMaxScore;
}
int m_iUseWordMaskNum;
vector<vector> m_vMaskCharNums;
};
2023年7月
class Solution {
public:
int maxScoreWords(vector& words, vector& letters, vector& score) {
m_c = words.size();
vector vHasChar(26);
for (const auto& ch : letters)
{
vHasChar[ch - ‘a’]++;
}
int iRet = 0;
const int iMaskNum = 1 << m_c;
for (int mask = 0; mask < iMaskNum; mask++)
{
int needChar[26] = { 0 };
for (int j = 0; j < m_c; j++)
{
if (mask & (1 << j))
{
for (const char& ch : words[j])
{
needChar[ch - ‘a’]++;
}
}
}
//字符不足
bool bEnough = true;
int iScource = 0;
for (int j = 0; j < 26; j++)
{
bEnough &= (needChar[j] <= vHasChar[j]);
iScource += score[j] * needChar[j];
}
if (bEnough)
{
iRet = max(iRet, iScource);
}
}
return iRet;
}
int m_c;
};
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
相關下載
想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 《喜缺全書算法冊》以原理、正確性證明、總結為主。 |
| 聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。 |
| 子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
測試環境
操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。
