怎样做视频电影网站,家具电商网站建设,wordpress generator,昆明网站建设时间#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
单词大师(100分) 评测功能需要 订阅专栏 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图 单词大师问题描述输入格式输出格式样例输入样例输出样例输入样例输出样例输入样例输出数据范围题解参考代码 单词大师
问题描述
给定一个字符串数组 w o r d s words words 和一个字符串 c h a r s chars chars。如果可以用 c h a r s chars chars 中的字母拼写出 w o r d s words words 中的某个单词则认为你掌握了这个单词。 w o r d s words words 中的字符仅由小写字母 a − z a-z a−z 和特殊字符 ? 组成其中 ? 可以代表任意一个字母。
注意拼写时 c h a r s chars chars 中的每个字母只能使用一次? 也只能使用一次。
请输出你能够拼写出的 w o r d s words words 中的单词数量。如果一个也拼写不出则输出 0 0 0。
输入格式
第一行输入一个整数 N N N表示数组 w o r d s words words 的长度。
接下来 N N N 行每行输入一个字符串表示 w o r d s words words 中的一个单词。
最后一行输入一个字符串 c h a r s chars chars。
其中 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100 1 ≤ w o r d [ i ] . l e n g t h , c h a r s . l e n g t h ≤ 100 1 \le word[i].length, chars.length \le 100 1≤word[i].length,chars.length≤100。
输出格式
输出一个整数表示你能够拼写出的 w o r d s words words 中的单词数量。
样例输入
4
cat
bt
hat
tree
atach??样例输出
3样例输入
3
hello
world
cloud
welldonehoneyr样例输出
2样例输入
3
apple
car
window
welldoneapplec?样例输出
2数据范围 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100 1 ≤ w o r d [ i ] . l e n g t h , c h a r s . l e n g t h ≤ 100 1 \le word[i].length, chars.length \le 100 1≤word[i].length,chars.length≤100
题解
这道题可以通过统计字符频率的方式来判断是否能拼写出每个单词。
首先统计 c h a r s chars chars 中每个字母出现的次数以及 ? 出现的次数。对于每个单词 w o r d word word统计其中每个字母出现的次数。遍历单词的每个字母如果该字母在 c h a r s chars chars 中出现的次数大于等于在 w o r d word word 中出现的次数则可以拼写否则如果 ? 的数量大于等于不足的字母数也可以拼写否则无法拼写该单词。如果能拼写该单词则答案加一。最后输出答案即可。
时间复杂度为 O ( N L ) O(NL) O(NL)其中 N N N 为单词数量 L L L 为单词的平均长度。空间复杂度为 O ( 1 ) O(1) O(1)因为只需要常数级的额外空间。
参考代码
Python
n int(input())
words []
for _ in range(n):words.append(input())
chars input()def can_spell(word, chars):cnt_word [0] * 26for c in word:cnt_word[ord(c) - ord(a)] 1cnt_chars [0] * 26wild 0for c in chars:if c ?:wild 1else:cnt_chars[ord(c) - ord(a)] 1for i in range(26):if cnt_word[i] cnt_chars[i]:if wild cnt_word[i] - cnt_chars[i]:wild - cnt_word[i] - cnt_chars[i]else:return Falsereturn Trueans 0
for word in words:if can_spell(word, chars):ans 1print(ans)Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();String[] words new String[n];for (int i 0; i n; i) {words[i] sc.next();}String chars sc.next();int ans 0;for (String word : words) {if (canSpell(word, chars)) {ans;}}System.out.println(ans);}private static boolean canSpell(String word, String chars) {int[] cntWord new int[26];for (char c : word.toCharArray()) {cntWord[c - a];}int[] cntChars new int[26];int wild 0;for (char c : chars.toCharArray()) {if (c ?) {wild;} else {cntChars[c - a];}}for (int i 0; i 26; i) {if (cntWord[i] cntChars[i]) {if (wild cntWord[i] - cntChars[i]) {wild - cntWord[i] - cntChars[i];} else {return false;}}}return true;}
}Cpp
#include iostream
#include vector
#include string
using namespace std;bool canSpell(string word, string chars) {vectorint cntWord(26, 0);for (char c : word) {cntWord[c - a];}vectorint cntChars(26, 0);int wild 0;for (char c : chars) {if (c ?) {wild;} else {cntChars[c - a];}}for (int i 0; i 26; i) {if (cntWord[i] cntChars[i]) {if (wild cntWord[i] - cntChars[i]) {wild - cntWord[i] - cntChars[i];} else {return false;}}}return true;
}int main() {int n;cin n;vectorstring words(n);for (int i 0; i n; i) {cin words[i];}string chars;cin chars;int ans 0;for (string word : words) {if (canSpell(word, chars)) {ans;}}cout ans endl;return 0;
}
