LeetCode刷题指南：使用数组高效拼写单词

问题描述

本题要求处理两个输入：一个词汇列表（字符串数组）words 和一个字母表（字符串）chars。任务是从chars中选择字母来拼写words中的单词。每个字母在每次拼写过程中只能使用一次。最终目标是计算出能够被完全拼写出的所有单词的总长度。

例如：

输入: words = ["cat", "bt", "hat", "tree"], chars = "atach"
输出: 6
解释: 可以拼写出的单词为 "cat" 和 "hat"，因此总长度为 6。

又如：

输入: words = ["hello", "world", "leetcode"], chars = "welldonehoneyr"
输出: 10
解释: 可以拼写出的单词为 "hello" 和 "world"，因此总长度为 10。

题目限制条件如下：

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• 所有字符串均由小写字母组成

解决方案

为了解决这个问题，我们首先需要统计chars中每个字母的数量。然后对于words中的每一个单词，检查是否可以从chars中取出足够的字母来拼写该单词。如果可以，则累加该单词的长度到最终结果中。

以下是使用C++实现的暴力解法：

bool canFormWord(string word, string chars) {
vector charCount(26, 0);
for (char c : chars) ++charCount[c - 'a'];
for (char c : word) if (--charCount[c - 'a'] <0) return false;
return true;
}
int countCharacters(vector& words, string chars) {
int totalLength = 0;
for (const auto& word : words) if (canFormWord(word, chars)) totalLength += word.size();
return totalLength;
}

为了提高效率，我们可以直接使用固定大小的数组来代替上述代码中的向量或哈希表，这样可以减少内存分配和访问的时间开销。下面是优化后的版本：

int countCharacters(vector& words, string chars) {
int charCount[26] = {0};
for (char c : chars) ++charCount[c - 'a'];
int totalLength = 0;
for (const auto& word : words) {
int tempCount[26] = {0};
bool canForm = true;
for (char c : word) if (++tempCount[c - 'a'] > charCount[c - 'a']) { canForm = false; break; }
if (canForm) totalLength += word.size();
}
return totalLength;
}

总结

通过使用固定大小的数组来统计字母出现次数，我们可以显著提高程序的性能，特别是在处理大量数据时。这种方法不仅简化了代码逻辑，还减少了不必要的内存操作，从而提升了整体效率。

参考资料

来源: 力扣（LeetCode）
链接: https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters