What is the main pattern used in 'Find Words That Can Be Formed by Characters'?

The main pattern is array scanning combined with a hash lookup for character frequency to verify each word independently.

Can I reuse the chars for multiple words?

No, each word must be validated independently against the original chars counts; characters cannot carry over.

What data structure efficiently tracks character counts?

A fixed-size array of length 26 or a hash table mapping characters to counts works best for fast O(1) lookups.

How do I handle words with repeated letters?

Check that the frequency of each letter in the word does not exceed the frequency in chars; otherwise, the word is invalid.

Is the sum of lengths or number of words returned?

You return the sum of lengths of all valid words, not the count of words.

#1160

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

拼写单词

给定一个字符串数组 words 和一个字符串 chars 。如果字符串可以由 chars 中的字符组成（每个字符在每个 words 中只能使用一次），则认为它是好的。返回 words 中所有好的字符串的长度之和。示例 1：输入： words = ["cat","bt","hat","tre…

数组哈希表字符串计数

题目描述

给定一个字符串数组 words 和一个字符串 chars。

如果字符串可以由 chars 中的字符组成（每个字符在每个 words 中只能使用一次），则认为它是好的。

返回 words 中所有好的字符串的长度之和。

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
words[i] 和 chars 中都仅包含小写英文字母

lightbulb

解题思路

方法一：计数

我们可以用一个长度为 $26$ 的数组 $cnt$ 统计字符串 $chars$ 中每个字母出现的次数。

然后遍历字符串数组 $words$ ，对于每个字符串 $w$ ，我们用一个长度为 $26$ 的数组 $wc$ 统计字符串 $w$ 中每个字母出现的次数，如果对于每个字母 $c$ ， $wc[c] \leq cnt[c]$ ，那么我们就可以用 $chars$ 中的字母拼写出字符串 $w$ ，否则我们无法拼写出字符串 $w$ 。如果可以拼写出字符串 $w$ ，那么我们就将字符串 $w$ 的长度加到答案中。

遍历结束后，即可得到答案。

时间复杂度 $(L)$ ，空间复杂度 $O(C)$ 。其中 $L$ 为题目中所有字符串的长度之和；而 $C$ 为字符集的大小，本题中 $C = 26$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        cnt = Counter(chars)
        ans = 0
        for w in words:
            wc = Counter(w)
            if all(cnt[c] >= v for c, v in wc.items()):
                ans += len(w)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m * k) where n is the length of chars, m is the number of words, and k is the average word length. Space complexity is O(1) since the frequency map uses a fixed-size array of 26 for lowercase letters.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to independent word checks to avoid overcounting characters.
question_mark
Use a fixed-size hash table for character counting to optimize for repeated lookups.
question_mark
Emphasize correctness over clever shortcuts; each word must validate against the chars map precisely.

warning

常见陷阱

外企场景

error
Reusing chars counts across multiple words without resetting for each word.
error
Neglecting words with repeated characters exceeding chars availability.
error
Confusing word length sum with word count; only lengths of valid words matter.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the list of words that can be formed instead of the sum of lengths.
arrow_right_alt
Allow unlimited reuse of characters from chars and sum lengths accordingly.
arrow_right_alt
Modify chars dynamically to remove used characters permanently across words.

help

常见问题

外企场景

继续练习

#1366 通过投票对团队排名 #819 最常见的单词 #811 子域名访问计数