LeetCode 1160. 拼写单词

2022-09-26 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1160. 拼写单词

题意分析

给一个字符表 chars 和一组单词 words。如果某个单词能用 chars 里的字母拼出来（每个字母最多用它在 chars 中出现的次数），就把它的长度累加进答案，最后返回总长度。

「每个字母只能用一次」是全题的核心：判定标准不是「这个字母在 chars 里出现过」，而是「这个字母在单词里的出现次数不超过它在 chars 里的出现次数」。把「存在性」误当成「可用次数」是最典型的错解。

每个单词的判定彼此独立，chars 不会因为拼了某个单词而被消耗掉——这是很多人第一次读题会搞错的地方，题目求的是各自独立可拼的单词长度之和，而不是尽可能多地拼出单词。

字符集限定为小写英文字母，只有 26 种。这条约束直接指向用定长数组代替哈希表，常数更小、代码更短，也更适合白板手写。

边界包括：空单词天然可拼、长度为 0 不影响答案；单词长度超过 chars 长度时必然拼不出；chars 里的多余字母不影响任何判定。

解法：字母频次计数

核心思路

朴素思路是对每个单词复制一份 chars，逐字符去里面找并删掉找到的那一个。这样是对的，但查找和删除都要扫一遍剩余字符，单个单词的代价退化到 $O( word \cdot chars )$，而且实现起来还要处理「删除后数组空洞」这类琐事。

瓶颈在于把「多重集合的包含关系」当成了逐个匹配的过程。观察判定条件本身：单词能拼出，当且仅当对 26 个字母中的每一个，单词里的出现次数都不超过 chars 里的出现次数。这是一个纯粹的按字母比较的条件，与字母的排列顺序毫无关系，所以完全不需要匹配，只需要计数。

于是先把 chars 压成一个长度 26 的频次数组 base，之后每个单词也压成频次数组 count，逐位比较即可。base 只统计一次并全程复用，正好对应「单词之间互不消耗」的题意。

实现上还可以再省一步：不必先把整个单词统计完再比较，而是边统计边判定。遍历单词时每读一个字母就把它的计数加一，并立刻检查是否已经超过 base——由此维护的不变量是：扫描到单词的第 i 个字符时，若循环还没有中断，则该单词的前缀 word[0..i] 的每个字母用量都没有超过 base。一旦某个字母越界，后面无论怎么读都只会更差，可以立即中断。

解题步骤

先扫一遍 chars，把每个字母的出现次数记进长度 26 的 base 数组。用 c - 'a' 把字符映射成下标，这是小写字母题的标准做法，比哈希表少一次散列计算。

base 在整个流程中只建一次且从不修改。这既是效率考虑，更是正确性要求：题意规定单词之间互不影响，若在判定时直接扣减 base，后面的单词就会因为前面的单词而拼不出。

对每个单词新建一个长度 26 的 count 数组，并用布尔量 canForm 标记结果。新建保证了单词之间互不干扰，26 个 int 的分配开销可以忽略。

遍历单词的每个字符：先 count[idx]++，再判断 count[idx] > base[idx]。先加后判的顺序很关键——判定的是「算上当前这个字符之后是否超量」，先判后加会漏掉恰好超出的那一次。

一旦超量就置 canForm 为 false 并 break。提前退出不影响正确性，因为字母用量只增不减，越界之后不可能再回到合法状态。

循环正常结束说明每个字母都够用，把单词长度累加进答案。全部单词处理完返回累计值。

以 words = ["cat","bt","hat","tree"]、chars = "atach" 走一遍。先统计 base：a 出现 2 次、t 出现 1 次、c 出现 1 次、h 出现 1 次，其余为 0。

处理 "cat"：读 c，count[c] = 1，不超过 base 的 1；读 a，count[a] = 1，不超过 2；读 t，count[t] = 1，不超过 1。循环走完，canForm 为真，答案加 3。

处理 "bt"：读 b，count[b] = 1，而 base[b] = 0，1 > 0 成立，立即置 false 并 break。注意此时 t 根本没被检查——提前退出正是这个意思。答案不变，仍是 3。

处理 "hat"：读 h 得 1 不超过 1，读 a 得 1 不超过 2，读 t 得 1 不超过 1，可拼，答案加 3 变成 6。

处理 "tree"：读 t，count[t] = 1 不超过 1；读 r，count[r] = 1 而 base[r] = 0，越界，break。答案仍是 6。

返回 6，与题目样例一致。若把判定误写成「字母是否出现过」，"tree" 里的两个 e 也会被放行（在 chars 含 e 的用例下），答案就会偏大；若判定时直接扣减 base，处理完 "cat" 后 t 被扣光，"hat" 就会被误判为不可拼，答案会偏小到 3。

代码实现

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( chars + L)$，其中 L 是所有单词长度之和。chars 统计一次，每个单词的每个字符最多被读一次，提前退出只会让实际耗时更少。

空间复杂度：$O(1)$，base 和 count 都是固定 26 个整数，与输入规模无关；返回值不计入额外空间。

关键点总结

判断「一个多重集合能否被另一个覆盖」时，标准做法是各自计数后逐项比较，而不是逐字符查找删除——顺序信息在这类问题里是无关变量，丢掉它就能把复杂度降一个量级。

字符集有限（26 个小写字母、128 个 ASCII）时优先用定长数组做计数，c - 'a' 的下标映射比哈希表快也更好写，面试白板上尤其如此。

参照集合（这里的 base）必须保持只读；只要题意是「各自独立判定」，就绝不能在判定过程中扣减它，否则处理顺序会影响结果。

边遍历边判定并提前退出，靠的是「用量单调不减」这条性质，凡是判定量单调的问题都可以用同样的方式剪枝。

面试视角：这题的价值在于说清「计数比较」与「逐个匹配」的差别，以及为什么用数组而不是 HashMap。被追问「如果字符集是任意 Unicode 呢」，答案是换成哈希表并只统计单词中出现过的字符；被追问「如果单词要真的消耗 chars、求最多能拼几个」，那就变成了另一类贪心/搜索问题，要主动点明题意差别。

易错点总结

错误写法：判定只看字母是否出现过，如 if (base[idx] == 0) → 用例 words = ["aa"], chars = "a"，两个 a 都被放行，返回 2，正确答案是 0。

错误写法：判定时直接扣减 base，如 base[idx]-- 后判负 → 用例 words = ["cat","hat"], chars = "atach"，处理完 "cat" 后 t 被消耗完，"hat" 被误判不可拼，返回 3，正确答案是 6。

错误写法：count 数组提到循环外复用且不清零 → 用例 words = ["a","a"], chars = "a"，第二个单词的 count[a] 累积成 2 超过 base，返回 1，正确答案是 2。

错误写法：先判断后自增，如 if (count[idx] >= base[idx]) { ... } count[idx]++; → 用例 words = ["a"], chars = "a"，0 >= 1 不成立看似正常，但用例 words = ["ab"], chars = "b" 中 a 的 0 >= 0 成立会误判，且恰好用满的情形也会被错杀。

错误写法：判定写成 count[idx] >= base[idx] → 用例 words = ["cat"], chars = "atach"，c 恰好用满时被判越界，返回 0，正确答案是 3。

错误写法：break 之后忘记置 canForm 为 false，只靠 break 退出 → 用例 words = ["bt"], chars = "atach"，退出循环后仍按可拼处理，答案多加 2。

错误写法：把答案累加成「可拼单词的个数」而不是长度之和 → 用例 words = ["cat","hat"], chars = "atach"，返回 2，正确答案是 6。

错误写法：用 word.length() 之外的量累加，比如累加 chars 的长度 → 用例 words = ["cat"], chars = "atach"，返回 5，正确答案是 3。

错误写法：假设字符可能是大写或含非字母而不做处理，仍用 c - 'a' → 用例含大写字母时下标为负，Java 抛越界异常；本题约束保证全小写，但把这个假设说清楚是必要的。

错误写法：为了「优化」先按长度排序并在第一个拼不出的单词处整体停止 → 用例 words = ["bt","cat"], chars = "atach"，"bt" 拼不出并不意味着后面的单词也拼不出，直接返回 0，正确答案是 3。

相似题目

题目	难度	考察点
383. 赎金信	简单	只判定单个字符串能否被覆盖，返回布尔值而非长度累加
242. 有效的字母异位词	简单	要求频次完全相等而非小于等于，可用一次加一次减后查全零
面试题 01.02. 判定是否互为字符重排	简单	字符集扩展到 ASCII，计数数组要开到 128
387. 字符串中的第一个唯一字符	简单	计数后还需第二次遍历按原顺序找首个频次为 1 的位置
451. 根据字符出现频率排序	中等	统计之后要按频次排序重建字符串，考察桶排序或堆
692. 前K个高频单词	中等	计数单位从字母变成单词，还要在频次相同时按字典序打破平局