題目鏈接：力扣
https://leetcode-cn.com/problems/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]，
本場游戲的「得分」是指：玩家所拼寫出的單詞集合里包含的所有字母的得分之和，
方法： 回溯法
class Solution {
private:
int size;
const int SIZE = 27;
vector<int> vct;//哈希表，用于記錄小寫字母出現的次數
vector<int> tmp;
vector<int> score;
vector<string> words;//存盤單詞
int maxS = 0;//最大的分
void backTrack(int index,int s)//i表示第幾個單詞，s表示得分
{
for(int i=index+1;i<size;i++)
{
if(!isValid(words[i])) continue;//字串里的字符湊不齊就跳過
//湊齊了
int s1 = s;
vector<int> pre = tmp;
for(int j=0;j<26;j++)
{
s1 += score[j]*tmp[j];//更新得分
vct[j]-=tmp[j];//更新vct
}
maxS = max(maxS,s1);
backTrack(i,s1);//回溯
for(int j=0;j<26;j++)
{
vct[j]+=pre[j];//更新vct
}
}
}
bool isValid(string str)//判斷字串內的字符是否符合條件
{
tmp = vector<int>(SIZE,0);
for(auto& ch:str)
{
tmp[ch-'a']++;
}
for(int i=0;i<26;i++)
{
if(tmp[i]>vct[i]) return false;
}
return true;
}
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
this->words = words;//將字串集合變為全域
this->score = score;
vct = vector<int>(SIZE,0);
for(int i=0;i<letters.size();i++)//更新哈希表
{
vct[letters[i]-'a']++;//對應的字母數量自加
}
size = words.size();//統計單詞數目
for(int i=0;i<size;i++)
{
if(!isValid(words[i])) continue;//字串里的字符湊不齊就跳過
int s = 0;//統計得分
vector<int> pre = tmp;
//湊齊了
for(int j=0;j<26;j++)
{
s += score[j]*tmp[j];//更新得分
vct[j]-=tmp[j];//更新vct
}
maxS = max(maxS,s);//更新最大得分
backTrack(i,s);//回溯
for(int j=0;j<26;j++)
{
vct[j]+=pre[j];//更新vct
}
}
return maxS;//回傳最大得分
}
};轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339701.html
標籤：其他