NeetCode #68LC-1160EasyArrays & Hashing
← Back to All Problems#68 · #1160 · Find Words That Can Be Formed by Characters(拼写单词)
📌 Problem Statement & Constraints
You are given an array of strings
words and a string chars. A string is good if it can be formed using only the letters of chars, each letter used at most as many times as it appears in chars. Return the sum of the lengths of all good strings. Constraints: 1 <= words.length <= 1000, 1 <= chars.length <= 100, all lowercase letters.💡 Core Algorithmic Approaches
- Count the available letters in
charsonce. - For each word, count its letters and verify that no letter is required more times than available.
- If the word passes, add its length to the total.
- The whole-word check is what distinguishes this from a mere character-set test -- multiplicity matters.
💻 Benchmark Python3 Implementation
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
from collections import Counter
avail = Counter(chars)
total = 0
for w in words:
need = Counter(w)
if all(need[ch] <= avail[ch] for ch in need):
total += len(w)
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(|chars| + sum of word lengths): each word is counted once and compared against the available letters.
💾 Space Complexity
O(k) for the two counters, with k <= 26.
⚠️ Interview Pitfalls & Follow-ups
- Checking only
set(w) <= set(chars): this ignores multiplicity, sochars = "a"would wrongly accept the word"aa". - Iterating
availinstead ofneed: you must check every letter the word needs, not every letter available. - Mutating the available counts across words: each word must be tested against the full original
chars.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Arrays & Hashing Problems
中文速览与面试要点
拼写单词
给你一份「词汇表」words 和一份「字母表」chars(字符串)。假如你可以用 chars 中的字母「拼写」出 words 中的某个「单词」,那么就称掌握该单词。注意:每次拼写时,chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和 。约束:1 ≤ words.length ≤ 1000;1 ≤ words[i].length, chars.length ≤ 100;所有字符串仅含小写英文字母。
核心要点
- 字母池计数 + 逐词校验(标准解) :先把 chars 统计成字母池 pool 。对每个单词 w,统计它需要的字母数 need ,若所有字母都满足 need[c] <= pool[c] ,则该单词可拼写。
- 为什么每个字母只能用一次 :因此必须做「计数比较」而非「集合包含」。集合只能判断字母是否存在,无法反映数量约束。
- 优化 :可以预先按长度降序排序或提前剪枝(单词比 chars 长时直接跳过),但非必需。
- 等价实现 :也可以用 Counter(w) - pool ,若结果为空字典则说明可拼写。
常见陷阱
- 用集合包含判断 : set(w) <= set(chars) 只检查字母是否存在,无法发现「chars 只有一个 a 但单词需要两个 a」的情况。必须比较计数。
- 对每个单词都重新统计 chars :会把 chars 的统计重复 n 次,应预先统计一次。
- 忘记「每次拼写独立」 :题目说「每次拼写时 chars 中的每个字母都只能用一次」,但不同单词之间是 独立 的(不是共享消耗)。若误以为共享,需要用回溯或删除已用字母,属于误读。
参考实现
from collections import Counter
class Solution:
def countCharacters(self, words: list[str], chars: str) -> int:
pool = Counter(chars)
total = 0
for w in words:
need = Counter(w)
if all(need[c] <= pool[c] for c in need):
total += len(w)
return total
# 用 Counter 减法判空的等价写法:
# if not (Counter(w) - pool): total += len(w)