
本文介绍如何高效判断多个目标字符串是否能由一个源字符字符串(每个字符仅可使用一次)完全构成,核心是利用 collections.Counter 的子集比较操作
本文介绍如何高效判断多个目标字符串是否能由一个源字符字符串(每个字符仅可使用一次)完全构成,核心是利用 `collections.counter` 的子集比较操作 `
在字符串构成性判断问题中,关键约束是:源字符串 chars 中的每个字符只能被使用一次,因此不能仅检查字符是否存在,而必须严格验证各字符的出现频次是否足以覆盖目标字符串中对应字符的需求。
错误解法(如提问中的原始代码)的问题在于:
- 循环内未设置有效退出机制(
break后仍执行ans += 1); - 频次比较逻辑不完整(仅单向检查
word_freq[char] > chars_freq[char],但未确保所有字符都满足条件); - 缺乏对“全量满足”的明确判定,导致计数恒增,结果失真。
✅ 正确做法是借助 collections.Counter 的内置比较语义:Counter(a) 当且仅当 <code>a 中每个字符的频次均不超过 b 中对应字符的频次——这恰好等价于“a 可由 b 构成”。
以下是完整、可运行的解决方案:
当现有的脚本或服务需要将作用域化的仓库工作委托给 Claude Code 并以编程方式消费结构化响应时,请使用 Claude Agent SDK for Python。
立即学习“Python免费学习笔记(深入)”;
from collections import Counter
def count_formable_words(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
# 示例调用
targets = ["cat", "bt", "hat", "tree"]
chars = "atach"
print(count_formable_words(targets, chars)) # 输出:2? 执行过程解析:
-
"cat"→Counter({'c':1,'a':1,'t':1}) → ✅ 成立 -
"bt"→{'b':1,'t':1},但chars中无'b'(频次为 0)→ ❌ 不成立 -
"hat"→{'h':1,'a':1,'t':1}⊆chars_freq→ ✅ 成立 -
"tree"→{'t':1,'r':1,'e':2},chars中无'r'、'e'→ ❌ 不成立
最终结果为2,符合预期。
⚠️ 注意事项:
-
Counter的操作是 Python 3.10+ 原生支持的语义;若使用旧版本,可用 <code>all(word_freq[c] 替代; - 该方法时间复杂度为 O(N + Σ|w|),其中 N 是
chars长度,Σ|w| 是所有目标词总长度,高效且易读; - 切勿手动遍历比较后未加条件控制就累加计数——逻辑完整性比循环技巧更重要。
掌握 Counter 的集合式比较能力,能让频次敏感的字符串判定问题从易错的手动校验,跃升为清晰、健壮、一行语义即达意的专业实现。

















