【回溯】1255. 得分最高的单词集合

本文涉及知识点

回溯
力扣难道：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

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛