CTF of Z2BNS
0%

拼写单词

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例1：

1
2
3
4
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例2：

1
2
3
4
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

  • `1 <= words.length <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • 所有字符串中都仅包含小写英文字母
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

定义一个大小为26的数组存储字母表chars字符串中各个字母的个数，遍历字符串数组words对每一个单词字符串先判断长度，如果大于chars长度可定不满足则进行下个字符串的遍历，否则遍历单词字符串，判断字母是否在字母表中存在，若存在则继续若不存在则不满足跳出循环并标记该单词为false，若单词标记为true则把长度累加到结果中。

c++代码：(执行用时68ms，击败97.50%，内存消耗16.5M，击败76.81%）

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
class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        //计数法
        int result=0;
        int len_word=0,len_chars=chars.length();
        int ch[26]={0};
        int tmp[26];
        //存储chars中每个字母的个数
        for(char c1:chars){
            ++ch[c1-97];
        }
        for(string word:words){
            bool flag=true;
            //每次字母表chars都应该被恢复原值
            copy(begin(ch),end(ch),begin(tmp));
            len_word=word.size();
            //若word长度大于chars长度，肯定不满足条件
            if(len_word>len_chars){
                continue;
            }else{
                for(char c2:word){
                    if(tmp[c2-97]==0){
                        flag=false;
                        break;
                    }else{
                        --tmp[c2-97];
                    }
                }
            }
            if(flag){
                result+=word.length();
            }
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：哈希表记数

思路和算法

显然，对于一个单词 word，只要其中的每个字母的数量都不大于 chars 中对应的字母的数量，那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量，再用一个哈希表存储 word 中每个字母的数量，最后将这两个哈希表的键值对逐一进行比较即可。

c++代码：(执行用时424ms，击败34.93%，内存消耗49.9M，击败30.08%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> chars_cnt;
        for (char c : chars)
            ++chars_cnt[c];
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> word_cnt;
            for (char c : word)
                ++word_cnt[c];
            bool is_ans = true;
            for (char c : word)
                if (chars_cnt[c] < word_cnt[c]) {
                    is_ans = false;
                    break;
                }
            if (is_ans)
                ans += word.size();
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为所有字符串的长度和。我们需要遍历每个字符串，包括 chars 以及数组 words 中的每个单词。

  • 空间复杂度：$O(S)$，其中 $S$ 为字符集大小，在本题中 $S$ 的值为 $26$（所有字符串仅包含小写字母）。程序运行过程中，最多同时存在两个哈希表，使用的空间均不超过字符集大小 $S$，因此空间复杂度为 $O(S)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

总的来说官方题解和我的思路还算一致，不过我的更像是直观上的解法，官方题解是经过总结认真思考后的题解简洁明了，题目也比较简单，没想到我提交的代码效率还挺高的，有点意外😏。另外官方题解有视频题解，可以了解一下。官方题解效率反而不是很高，应该要先判断一下单词长度与字母表长度，若是长度不符就应该直接跳过进行下一个单词，而官方题解还是要进行单词字母计数与字母表中的计数进行比较，还有就是官方题解要遍历每一个单词中的所有字符，我的方法是只要遇到不满足条件的字符就终止了，所以比官方题解效率要高一些。

------------- THE END! THANKS! -------------