LeetCode 1160. 拼写单词
题目描述
题意分析
给定候选单词列表和一组可用字符
chars。分别判断每个单词能否用这些字符拼出，单词中每出现一次某个字母，就需要消耗chars中该字母的一次出现。不同单词独立判断，每个单词开始时都拥有完整的字符资源，不是让所有单词共同竞争同一份字符。最后返回所有可拼单词的长度总和，既不是单词数量，也不是最长单词长度。列表中的相同单词出现多次时，应分别计入。
解法：字母频次计数
核心思路
[!blue]
能否拼出一个单词只取决于每种字母的需求次数是否不超过可用次数，字母在
chars中的原始顺序不重要。因此先用长度为26的base数组统计可用小写字母频次，之后让这份统计保持只读，供所有单词复用。对于一个新单词，创建全零的需求数组
count。逐字读取单词，增加对应需求次数后立即与base比较。只要某种字母需求超过供给，这个单词就无法组成；后续读取只会继续增加需求，不可能把超出的次数抵消，所以可以提前结束本词检查。如果整词读完都没有超量，说明每种字母的供给都足够。不同字母之间互不冲突，分别选取所需次数就能组成整个单词，因此这些频次条件不仅必要，也足够。此时把整个单词长度加到答案。
下一单词重新建立需求计数，不修改
base，这样之前的可拼或不可拼结果都不会影响它。每个单词只做一次独立判定，自然保留了重复列表项的贡献。
解题步骤
- 统计
chars中每种小写字母的出现次数，保存为基础供给base。- 对每个单词创建新的需求数组，并先假定它可以组成。
- 逐字增加需求，任何字母超过供给时标记失败并结束本词检查。
- 完整检查通过后，把该单词长度加入结果。
- 独立检查完全部单词，返回累计长度。
代码实现
class Solution {
public int countCharacters(String[] words, String chars) {
int[] base = new int[26];
for (char c : chars.toCharArray()) {
base[c - 'a']++;
}
int res = 0;
for (String word : words) {
// 每个单词独立统计需求，不能沿用上一个词的用量。
int[] count = new int[26];
boolean canForm = true;
for (char c : word.toCharArray()) {
int idx = c - 'a';
count[idx]++;
// 需求已经超过供给，继续读后缀也无法恢复合法。
if (count[idx] > base[idx]) {
canForm = false;
break;
}
}
if (canForm) {
res += word.length();
}
}
return res;
}
}
func countCharacters(words []string, chars string) int {
base := make([]int, 26)
for i := 0; i < len(chars); i++ {
base[chars[i]-'a']++
}
res := 0
for _, word := range words {
// 每个单词独立统计需求，不能沿用上一个词的用量。
count := make([]int, 26)
canForm := true
for i := 0; i < len(word); i++ {
idx := word[i] - 'a'
count[idx]++
// 需求已经超过供给，继续读后缀也无法恢复合法。
if count[idx] > base[idx] {
canForm = false
break
}
}
if canForm {
res += len(word)
}
}
return res
}
复杂度分析
- 时间复杂度：
O(C + L)，其中C为chars长度，L为所有候选单词长度之和。每个字符至多检查一次，固定26项的初始化不改变该量级。- 空间复杂度：Go 使用两组固定长度计数，辅助空间为
O(1)；Java 当前实现调用toCharArray()创建字符副本，辅助空间上界为O(C + Lmax + 26)，其中Lmax是最长单词长度。
关键点总结
[!green]
- 字符存在不代表数量足够，必须比较频次而不是集合成员关系。
- 基础供给保持只读，需求计数按单词重建，表达独立使用资源。
- 需求一旦超量就不可恢复，可以立即停止检查当前单词。
- 检查通过后贡献的是完整单词长度，每个列表项分别计入。
易错点总结
[!yellow]
- 永久扣减共享供给：后面的单词本应重新获得全部字符，不能受前词消耗影响。
- 复用需求数组却不清零：会错误累加不同单词的需求。
- 只检查字母是否出现过：单词可能多次需要同一个字母，字符数量也必须足够。
- 只统计成功单词个数：题目要求累加长度，需要加上
word.length()或len(word)。- 按字典去重单词列表：重复出现的可拼单词也分别贡献长度，不能擅自删除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 383. 赎金信 | 简单 | 对每个候选词分别复用字符供给是否足够的频次判断，字符资源不在不同单词间累计消耗。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！