
本文介绍使用 Python 的 Counter 实现高效判断:给定源字符串 chars,检查目标字符串列表中每个字符串是否能由 chars 中的字符不重复使用地拼出,并统计满足条件的数量。
本文介绍使用 python 的 counter 实现高效判断:给定源字符串 `chars`,检查目标字符串列表中每个字符串是否能由 `chars` 中的字符**不重复使用**地拼出,并统计满足条件的数量。
在字符串构造类问题中,一个常见需求是:判断某个单词(或字符串)能否仅使用给定字符集中的字符、且每个字符最多使用一次来完整拼出。例如:
from collections import Counter targets = ["cat", "bt", "hat", "tree"] chars = "atach"
期望结果为 2——因为只有 "cat"(需 c/a/t)和 "hat"(需 h/a/t)能被 chars="atach"(含 a×2, t, c, h)完全覆盖;而 "bt" 缺少 'b',"tree" 需要两个 'e' 和两个 'r',但 chars 中均未出现。
✅ 正确解法:利用 Counter 的子集比较
collections.Counter 支持直接比较操作符 ,语义为:<strong>左侧 Counter 的每种字符频次均不超过右侧对应字符频次</strong>,即“左侧可被右侧完全覆盖”。这恰好对应本题的“能否由 <code>chars 构成”的数学定义。
from collections import Counter
def count_characters_in_string(targets, chars):
chars_freq = Counter(chars)
ans = 0
for word in targets:
word_freq = Counter(word)
if word_freq <= chars_freq: # 关键:原子化判断,无需手动遍历
ans += 1
return ans
# 测试
print(count_characters_in_string(targets, chars)) # 输出:2❌ 原代码错误分析
原实现中存在两个关键缺陷:
当现有的脚本或服务需要将作用域化的仓库工作委托给 Claude Code 并以编程方式消费结构化响应时,请使用 Claude Agent SDK for Python。
立即学习“Python免费学习笔记(深入)”;
-
逻辑短路后仍计数:内层
for char in word:循环中,一旦发现某字符不足就break,但后续仍无条件执行ans += 1,导致所有单词都被计入; -
比较逻辑错误:写的是
if word_freq[char] > chars_freq[char],意图是“若单词中某字符用量超限则跳过”,但即使触发break,程序也未阻止ans自增。
更严重的是,该循环未设置标志位(如 valid = True),无法可靠传达“当前单词是否整体合法”。
? 进阶优化建议
-
提前终止构建:若
len(word) > len(chars),可直接跳过(长度不可能满足); -
复用 Counter 对象:对长列表,避免重复创建
Counter(chars),应预先计算并复用; -
函数式写法(简洁版):
from collections import Counter def count_constructible(targets, chars): chars_cnt = Counter(chars) return sum(Counter(w) <= chars_cnt for w in targets)
✅ 总结
使用 Counter 的 操作符是解决此类“字符资源约束下的字符串可构造性”问题的最优实践:语义清晰、代码简洁、性能优异(时间复杂度 O(N + M),N 为总字符数,M 为单词数)。务必避免手动遍历比对频次,既易错又低效。

















