【搜索难题】力扣1255-得分最高的单词集合

  |  

摘要: 枚举集合

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


常见的枚举方式位运算操作 等文章中,我们介绍了常见的枚举方式。本文看一个相关的问题,难点就在于正确地将子集枚举出来。

$1 题目

1255. 得分最高的单词集合

你将会得到一份单词表 words,一个字母表 letters (可能会有重复字母),以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」:能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中,分数最高的单词集合的得分。

单词拼写游戏的规则概述如下:

玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母,但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分(使用)一次。
根据字母得分情况表score,字母 ‘a’, ‘b’, ‘c’, … , ‘z’ 对应的得分分别为 score[0], score[1], …, score[25]。
本场游戏的「得分」是指:玩家所拼写出的单词集合里包含的所有字母的得分之和。

提示:

1
2
3
4
5
6
7
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] 只包含小写的英文字母。

示例 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 中的单词。

$2 题解

算法: 枚举子集

单词一共15个,枚举15个单词的子集,check 该子集是否可以取到。

check 过程:枚举集合中的每个单词,将单词的字符计数累加起来,如果枚举到某个词,将其字符计数累加之后超出了限制,则 check 不通过。

如果最终 check 通过,则更新答案。

枚举过程可以用位运算进行递推枚举,也可以用 DFS 递归枚举,DFS 的好处是如果某个更小的子集 check 没通过,会提前剪枝,不会枚举更大的子集。

代码1: 迭代枚举 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
int n = words.size();
vector<int> word_score(n);
word_cnts.assign(n, vector<int>(26, 0));
for(int i = 0; i < n; ++i)
{
int s = 0;
for(char ch: words[i])
{
++word_cnts[i][ch - 'a'];
s += score[ch - 'a'];
}
word_score[i] = s;
}
cnts.assign(26, 0);
for(char ch: letters)
++cnts[ch - 'a'];
int ans = 0;
// 迭代子集枚举
for(int choose = 1; choose < (1 << n); ++choose)
{
vector<int> choose_cnt(26);
bool flag = true;
int cand = 0;
for(int i = 0; i < n; ++i)
{
if(choose >> i & 1)
{
cand += word_score[i];
for(int j = 0; j < 26; ++j)
{
choose_cnt[j] += word_cnts[i][j];
if(choose_cnt[j] > cnts[j])
{
flag = false;
break;
}
}
}
if(!flag)
break;
}
if(flag)
ans = max(ans, cand);
}
return ans;
}

private:
vector<int> cnts;
vector<vector<int>> word_cnts;
};

代码2: 递归枚举 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
int n = words.size();
word_score.assign(n, 0);
word_cnts.assign(n, vector<int>(26, 0));
for(int i = 0; i < n; ++i)
{
int s = 0;
for(char ch: words[i])
{
++word_cnts[i][ch - 'a'];
s += score[ch - 'a'];
}
word_score[i] = s;
}
cnts.assign(26, 0);
for(char ch: letters)
++cnts[ch - 'a'];
int ans = 0;
vector<int> remain_cnt = cnts;
dfs(0, ans, 0, remain_cnt, n);
return ans;
}

private:
vector<int> word_score;
vector<int> cnts;
vector<vector<int>> word_cnts;

// 递归子集枚举
void dfs(int pos, int& ans, int s, vector<int>& remain_cnt, const int n)
{
if(pos == n)
{
ans = max(ans, s);
return;
}
// 不选 words[pos]
dfs(pos + 1, ans, s, remain_cnt, n);
// 选 words[pos]
if(check(remain_cnt, pos))
{
for(int i = 0; i < 26; ++i)
remain_cnt[i] -= word_cnts[pos][i];
dfs(pos + 1, ans, s + word_score[pos], remain_cnt, n);
for(int i = 0; i < 26; ++i)
remain_cnt[i] += word_cnts[pos][i];
}
}

bool check(const vector<int>& remain_cnt, int pos)
{
for(int i = 0; i < 26; ++i)
if(remain_cnt[i] < word_cnts[pos][i])
return false;
return true;
}
};

Share