赞
踩
有一个字符串数组 words
和一个字符串 chars
。
假如可以用 chars
中的字母拼写出 words
中的某个“单词”
(字符串),那么我们就认为你掌握了这个单词。
words
的字符仅由 a-z
英文小写字母组成,例如 “abc”
chars
由 a-z
英文小写字母和 “?”
组成。其中英文问号 “?”
表示万能字符,能够在拼写时当做任意一个英文字母。例如:“?”
可以当做 “a”
等字母。
注意:每次拼写时,chars
中的每个字母和万能字符都只能使用一次。
输出词汇表 words
中你掌握的所有单词的个数。没有掌握任何单词,则输出 0
。
第 1
行输入数组 words
的个数,记为 N
。 从第 2
行开始到第 N+1
行一次输入数组 words
的每个字符串元素。 第 N+2
行输入字符串 chars
。
输出一个整数,表示词汇表 words
中你掌握的单词个数。
4
cat
bt
hat
tree
atach
2
atach
可以拼写出单词cat
和hat
,因此掌握的单词是2
个。
4
cat
bt
hat
tree
at?ch
3
at?ch
可以拼写出单词cat
、hat
和bt
,因此掌握的单词是3
个。
统计元素频率,很显然需要使用哈希表进行。
唯一需要特殊处理的就是字符?
可以代表万能字符。
假设某一单词word
和字符串chars
对应的计数器分别为cnt_word
和cnt_chars
,问号字符?
出现的次数为num
。那么在逐一比较word
中字符出现次数和chars
中元素出现字符时,若出现cnt_word[k] > cnt_chars[k]
,则可以使用cnt_word[k] - cnt_chars[k]
个?
来作为万能字符。若发现此时?
出现的次数为num
已经小于cnt_word[k] - cnt_chars[k]
,则无法拼凑出单词word
。
# 题目:【哈希表】2023C-掌握单词个数 # 分值:100 # 作者:许老师-闭着眼睛学数理化 # 算法:哈希表 # 代码看不懂的地方,请直接在群上提问 # 检查cnt_chars能否完全拼写出cnt_word的函数 # 其中num为cnt_chars中问号字符的个数 def check(cnt_chars, cnt_word, num): # 遍历cnt_word中的所有键k for k in cnt_word.keys(): # 如果chars中k出现的个数大于等于word # 则可以直接使用这些字符k来拼写出word中的k if cnt_chars[k] >= cnt_word[k]: continue # 如果chars中k出现的个数小于word else: # 则需要使用cnt_word[k] - cnt_chars[k]个万能字符 # 才能使得字符k能够被在chars中被全部拼写 num -= cnt_word[k] - cnt_chars[k] # 若使用完之后,num的个数小于0,则说明万能字符的个数不足 # 不可能完成拼写 # 直接返回False if num < 0: return False # 如果能够顺利退出上述循环,即通过了检查,返回True return True from collections import Counter # 输入words的个数 n = int(input()) words = list() # 循环n次,输入n个单词 for _ in range(n): words.append(input()) # 输入chars字符串 chars = input() # 获得chars字符串对应的元素频率哈希表 cnt_chars = Counter(chars) ans = 0 # 获得chars中问号字符的个数 num = cnt_chars["?"] # 遍历words中的每一个单词word for word in words: # 构建word对应的哈希表计数器 cnt_word = Counter(word) # 调用check函数,将结果加入ans中 ans += int(check(cnt_chars, cnt_word, num)) print(ans)
import java.util.*; public class Main { static boolean check(HashMap<Character, Integer> cntChars, HashMap<Character, Integer> cntWord, int num) { for (char k : cntWord.keySet()) { if (cntChars.getOrDefault(k, 0) >= cntWord.getOrDefault(k, 0)) { continue; } else { num -= cntWord.getOrDefault(k, 0) - cntChars.getOrDefault(k, 0); if (num < 0) { return false; } } } return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = Integer.parseInt(scanner.nextLine()); List<String> words = new ArrayList<>(); for (int i = 0; i < n; i++) { words.add(scanner.nextLine()); } String chars = scanner.nextLine(); HashMap<Character, Integer> cntChars = new HashMap<>(); for (char c : chars.toCharArray()) { cntChars.put(c, cntChars.getOrDefault(c, 0) + 1); } int ans = 0; int num = cntChars.getOrDefault('?', 0); for (String word : words) { HashMap<Character, Integer> cntWord = new HashMap<>(); for (char c : word.toCharArray()) { cntWord.put(c, cntWord.getOrDefault(c, 0) + 1); } ans += check(cntChars, cntWord, num) ? 1 : 0; } System.out.println(ans); } }
#include <iostream> #include <unordered_map> #include <vector> using namespace std; bool check(unordered_map<char, int>& cntChars, unordered_map<char, int>& cntWord, int num) { for (auto& kv : cntWord) { char k = kv.first; if (cntChars[k] >= cntWord[k]) { continue; } else { num -= cntWord[k] - cntChars[k]; if (num < 0) { return false; } } } return true; } int main() { int n; cin >> n; cin.ignore(); // To consume the newline character vector<string> words(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } cin.ignore(); // To consume the newline character string chars; getline(cin, chars); unordered_map<char, int> cntChars; for (char c : chars) { cntChars[c]++; } int ans = 0; int num = cntChars['?']; for (string& word : words) { unordered_map<char, int> cntWord; for (char c : word) { cntWord[c]++; } ans += check(cntChars, cntWord, num) ? 1 : 0; } cout << ans << endl; return 0; }
时间复杂度:O(NM)
。其中M
为每一个单词word
的字符种类个数,最高为26
。单次调用check()
函数的时间复杂度为O(M)
。
空间复杂度:O(N)
。
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336
了解更多
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。