算法leetcode

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

字数统计: 1.3k字   |   阅读时长: 6分
,

摘要: 枚举集合

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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