🍭 大家好這里是清隆學(xué)長 ，一枚熱愛算法的程序員

? 本系列打算持續(xù)跟新華為OD-C/D卷的三語言AC題解

💻 ACM銀牌🥈| 多次AK大廠筆試 ｜ 編程一對一輔導(dǎo)

👏 感謝大家的訂閱? 和 喜歡💗

📎在線評測鏈接

單詞大師(100分)

🌍 評測功能需要 訂閱專欄 后私信聯(lián)系清隆解鎖～

🍓OJ題目截圖

🥮 單詞大師

問題描述

給定一個字符串?dāng)?shù)組 $words$ 和一個字符串 $chars$。如果可以用 $chars$ 中的字母拼寫出 $words$ 中的某個單詞，則認為你掌握了這個單詞。$words$ 中的字符僅由小寫字母 $a?z$ 和特殊字符 ? 組成，其中 ? 可以代表任意一個字母。

注意：拼寫時，$chars$ 中的每個字母只能使用一次，? 也只能使用一次。

請輸出你能夠拼寫出的 $words$ 中的單詞數(shù)量。如果一個也拼寫不出，則輸出 $0$。

輸入格式

第一行輸入一個整數(shù) $N$，表示數(shù)組 $words$ 的長度。

接下來 $N$ 行，每行輸入一個字符串，表示 $words$ 中的一個單詞。

最后一行輸入一個字符串 $chars$。

其中，$1\le N\le 100$，$1\le word[i].length,chars.length\le 100$。

輸出格式

輸出一個整數(shù)，表示你能夠拼寫出的 $words$ 中的單詞數(shù)量。

樣例輸入

4
cat
bt
hat
tree
atach??

樣例輸出

3

樣例輸入

3
hello
world
cloud
welldonehoneyr

樣例輸出

2

樣例輸入

3
apple
car
window
welldoneapplec?

樣例輸出

2

數(shù)據(jù)范圍

• $1\le N\le 100$
• $1\le word[i].length,chars.length\le 100$

題解

這道題可以通過統(tǒng)計字符頻率的方式來判斷是否能拼寫出每個單詞。

1. 首先統(tǒng)計 $chars$ 中每個字母出現(xiàn)的次數(shù)，以及 ? 出現(xiàn)的次數(shù)。
2. 對于每個單詞 $word$，統(tǒng)計其中每個字母出現(xiàn)的次數(shù)。
3. 遍歷單詞的每個字母，如果該字母在 $chars$ 中出現(xiàn)的次數(shù)大于等于在 $word$ 中出現(xiàn)的次數(shù)，則可以拼寫；否則，如果 ? 的數(shù)量大于等于不足的字母數(shù)，也可以拼寫；否則，無法拼寫該單詞。
4. 如果能拼寫該單詞，則答案加一。
5. 最后輸出答案即可。

時間復(fù)雜度為 $O(NL)$，其中 $N$ 為單詞數(shù)量，$L$ 為單詞的平均長度。空間復(fù)雜度為 $O(1)$，因為只需要常數(shù)級的額外空間。

參考代碼

• 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) {vector<int> cntWord(26, 0);for (char c : word) {cntWord[c - 'a']++;}vector<int> 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;vector<string> 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;
}