企业官网建设流程全解析

LeetCode 1160「拼写单词」多解法详解：字符频率计数与定长数组优化

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文围绕 LeetCode 1160「Find Words That Can Be Formed by Characters（拼写单词）」展开，系统讲解如何用字符频率计数判断单词是否可由给定字符串chars拼成，并给出「两遍哈希表」「单遍哈希表」「定长 26 数组哈希表」三种递进解法及完整的多语言实现。本仓库 leetcode 的 Java 版实现 与 Kotlin 版实现 与本文算法一一对应。读完本文，你将掌握频率计数类字符串问题的通用套路，并能在面试中根据数据规模自主选择哈希表与数组两种实现。

问题定义与前置知识

题目要求：给定一个字符串数组words和一个字符池字符串chars，统计所有「能由chars中的字符拼成」的单词，返回这些单词长度之和。

判定规则只有一个核心点：单词中每个字符出现的次数，都必须小于等于该字符在chars中出现的次数。注意这不是子序列或子串匹配，顺序无关，只看字符的多重集合（multiset）是否被包含。

动手解题前，你需要具备以下基础：

• 哈希表 / 字典：用于统计字符频率并进行 O(1) 查找；
• 字符串遍历：逐字符遍历以构建频率计数；
• 定长数组当哈希表：当字符集已知且有限（本题为 26 个小写字母）时，用int[26]替代哈希表，是本题乃至很多计数类题目的关键优化手段。

在仓库的 Kotlin 实现 中可以看到groupingBy { it }.eachCount()这种用标准库直接统计频率的写法，本质与手写哈希表相同。

解法一：哈希表（两遍扫描）

思路

先遍历一遍chars建立全局频率表count；然后对每个单词再遍历一遍，建立该单词自己的频率表cur_word，逐字符核对cur_word[c] <= count[c]。之所以叫「两遍」，是因为对每个单词而言，先完整构建其频率表（第一遍），再整体比较（第二遍）。

算法步骤

1. 构建chars的频率表count；
2. 对每个单词w：
   • 构建单词频率表cur_word；
   • 检查cur_word中每个字符的出现次数是否均不超过count中的对应值；
   • 若合法，将len(w)累加到结果res；
3. 返回res。

多语言实现

class Solution: def countCharacters(self, words: List[str], chars: str) -> int: count = Counter(chars) res = 0 for w in words: cur_word = Counter(w) good = True for c in cur_word: if cur_word[c] > count[c]: good = False break if good: res += len(w) return res

public class Solution { public int countCharacters(String[] words, String chars) { Map<Character, Integer> count = new HashMap<>(); for (char c : chars.toCharArray()) { count.put(c, count.getOrDefault(c, 0) + 1); } int res = 0; for (String w : words) { Map<Character, Integer> curWord = new HashMap<>(); for (char c : w.toCharArray()) { curWord.put(c, curWord.getOrDefault(c, 0) + 1); } boolean good = true; for (char c : curWord.keySet()) { if (curWord.get(c) > count.getOrDefault(c, 0)) { good = false; break; } } if (good) { res += w.length(); } } return res; } }

class Solution { public: int countCharacters(vector<string>& words, string chars) { unordered_map<char, int> count; for (char c : chars) { count[c]++; } int res = 0; for (const string& w : words) { unordered_map<char, int> curWord; for (char c : w) { curWord[c]++; } bool good = true; for (const auto& p : curWord) { if (p.second > count[p.first]) { good = false; break; } } if (good) { res += w.size(); } } return res; } };

class Solution { /** * @param {string[]} words * @param {string} chars * @return {number} */ countCharacters(words, chars) { const count = {}; for (const c of chars) { count[c] = (count[c] || 0) + 1; } let res = 0; for (const w of words) { const curWord = {}; for (const c of w) { curWord[c] = (curWord[c] || 0) + 1; } let good = true; for (const c in curWord) { if (curWord[c] > (count[c] || 0)) { good = false; break; } } if (good) { res += w.length; } } return res; } }

public class Solution { public int CountCharacters(string[] words, string chars) { Dictionary<char, int> count = new Dictionary<char, int>(); foreach (char c in chars) { if (!count.ContainsKey(c)) count[c] = 0; count[c]++; } int res = 0; foreach (string w in words) { Dictionary<char, int> curWord = new Dictionary<char, int>(); foreach (char c in w) { if (!curWord.ContainsKey(c)) curWord[c] = 0; curWord[c]++; } bool good = true; foreach (var kvp in curWord) { int available = count.ContainsKey(kvp.Key) ? count[kvp.Key] : 0; if (kvp.Value > available) { good = false; break; } } if (good) { res += w.Length; } } return res; } }

func countCharacters(words []string, chars string) int { count := make(map[rune]int) for _, c := range chars { count[c]++ } res := 0 for _, w := range words { curWord := make(map[rune]int) for _, c := range w { curWord[c]++ } good := true for c, cnt := range curWord { if cnt > count[c] { good = false break } } if good { res += len(w) } } return res }

class Solution { fun countCharacters(words: Array<String>, chars: String): Int { val count = mutableMapOf<Char, Int>() for (c in chars) { count[c] = count.getOrDefault(c, 0) + 1 } var res = 0 for (w in words) { val curWord = mutableMapOf<Char, Int>() for (c in w) { curWord[c] = curWord.getOrDefault(c, 0) + 1 } var good = true for ((c, cnt) in curWord) { if (cnt > count.getOrDefault(c, 0)) { good = false break } } if (good) { res += w.length } } return res } }

class Solution { func countCharacters(_ words: [String], _ chars: String) -> Int { var count = [Character: Int]() for c in chars { count[c, default: 0] += 1 } var res = 0 for w in words { var curWord = [Character: Int]() for c in w { curWord[c, default: 0] += 1 } var good = true for (c, cnt) in curWord { if cnt > (count[c] ?? 0) { good = false break } } if good { res += w.count } } return res } }

impl Solution { pub fn count_characters(words: Vec<String>, chars: String) -> i32 { let mut count = HashMap::new(); for c in chars.chars() { *count.entry(c).or_insert(0) += 1; } let mut res = 0; for w in &words { let mut cur_word = HashMap::new(); for c in w.chars() { *cur_word.entry(c).or_insert(0) += 1; } let mut good = true; for (&c, &cnt) in &cur_word { if cnt > *count.get(&c).unwrap_or(&0) { good = false; break; } } if good { res += w.len() as i32; } } res } }

复杂度分析

• 时间复杂度：O(n + m·k)，其中 n 为chars的长度，m 为单词个数，k 为单词平均长度；
• 空间复杂度：O(1)——因为字符集最多 26 个不同小写字母，哈希表规模有常数上界。

符号约定：n 为chars长度，m 为words中的单词数，k 为每个单词的平均长度。

仓库中的 Java 直观版实现 采用的就是「先建chars频率数组、再为每个单词建频率数组、最后逐下标比较」的两遍思路，只是把哈希表换成了int[26]，对应下面解法三。

解法二：哈希表（单遍扫描，支持提前终止）

思路

解法一需要先完整构建每个单词的频率表再比较；解法二则改为边遍历边校验：遍历单词字符的同时在临时表中累加计数，一旦发现某个字符的累计数超过chars中的可用数，立即标记该单词非法并 break，从而对非法单词实现提前终止，减少不必要的遍历。

算法步骤

1. 构建chars的频率表count；
2. 对每个单词：
   • 初始化空表cur_word；
   • 逐字符遍历：cur_word[c]自增，若cur_word[c] > count[c]，标记非法并 break；
   • 若合法，累加len(w)到res；
3. 返回res。

多语言实现

class Solution: def countCharacters(self, words: List[str], chars: str) -> int: count = Counter(chars) res = 0 for w in words: cur_word = defaultdict(int) good = True for c in w: cur_word[c] += 1 if cur_word[c] > count[c]: good = False break if good: res += len(w) return res

public class Solution { public int countCharacters(String[] words, String chars) { Map<Character, Integer> count = new HashMap<>(); for (char c : chars.toCharArray()) { count.put(c, count.getOrDefault(c, 0) + 1); } int res = 0; for (String w : words) { Map<Character, Integer> curWord = new HashMap<>(); boolean good = true; for (char c : w.toCharArray()) { curWord.put(c, curWord.getOrDefault(c, 0) + 1); if (curWord.get(c) > count.getOrDefault(c, 0)) { good = false; break; } } if (good) { res += w.length(); } } return res; } }

class Solution { public: int countCharacters(vector<string>& words, string chars) { unordered_map<char, int> count; for (char c : chars) { count[c]++; } int res = 0; for (const string& w : words) { unordered_map<char, int> curWord; bool good = true; for (char c : w) { curWord[c]++; if (curWord[c] > count[c]) { good = false; break; } } if (good) { res += w.size(); } } return res; } };

class Solution { /** * @param {string[]} words * @param {string} chars * @return {number} */ countCharacters(words, chars) { const count = {}; for (const c of chars) { count[c] = (count[c] || 0) + 1; } let res = 0; for (const w of words) { const curWord = {}; let good = true; for (const c of w) { curWord[c] = (curWord[c] || 0) + 1; if (curWord[c] > (count[c] || 0)) { good = false; break; } } if (good) { res += w.length; } } return res; } }

public class Solution { public int CountCharacters(string[] words, string chars) { Dictionary<char, int> count = new Dictionary<char, int>(); foreach (char c in chars) { if (!count.ContainsKey(c)) count[c] = 0; count[c]++; } int res = 0; foreach (string w in words) { Dictionary<char, int> curWord = new Dictionary<char, int>(); bool good = true; foreach (char c in w) { if (!curWord.ContainsKey(c)) curWord[c] = 0; curWord[c]++; int available = count.ContainsKey(c) ? count[c] : 0; if (curWord[c] > available) { good = false; break; } } if (good) { res += w.Length; } } return res; } }

func countCharacters(words []string, chars string) int { count := make(map[rune]int) for _, c := range chars { count[c]++ } res := 0 for _, w := range words { curWord := make(map[rune]int) good := true for _, c := range w { curWord[c]++ if curWord[c] > count[c] { good = false break } } if good { res += len(w) } } return res }

class Solution { fun countCharacters(words: Array<String>, chars: String): Int { val count = mutableMapOf<Char, Int>() for (c in chars) { count[c] = count.getOrDefault(c, 0) + 1 } var res = 0 for (w in words) { val curWord = mutableMapOf<Char, Int>() var good = true for (c in w) { curWord[c] = curWord.getOrDefault(c, 0) + 1 if (curWord[c]!! > count.getOrDefault(c, 0)) { good = false break } } if (good) { res += w.length } } return res } }

class Solution { func countCharacters(_ words: [String], _ chars: String) -> Int { var count = [Character: Int]() for c in chars { count[c, default: 0] += 1 } var res = 0 for w in words { var curWord = [Character: Int]() var good = true for c in w { curWord[c, default: 0] += 1 if curWord[c]! > (count[c] ?? 0) { good = false break } } if good { res += w.count } } return res } }

impl Solution { pub fn count_characters(words: Vec<String>, chars: String) -> i32 { let mut count = HashMap::new(); for c in chars.chars() { *count.entry(c).or_insert(0) += 1; } let mut res = 0; for w in &words { let mut cur_word = HashMap::new(); let mut good = true; for c in w.chars() { *cur_word.entry(c).or_insert(0) += 1; if cur_word[&c] > *count.get(&c).unwrap_or(&0) { good = false; break; } } if good { res += w.len() as i32; } } res } }

复杂度分析

• 时间复杂度：O(n + m·k)（平均情况下因提前终止而更省）；
• 空间复杂度：O(1)，字符种类上限为 26。

符号约定同上：n 为chars长度，m 为单词数，k 为单词平均长度。

与解法一的取舍

解法二的优势在于尽早发现非法单词：对于「cat」这样的短单词影响不大，但对于长且明显超额的单词（如由 1000 个z组成而chars里只有一个z），在遍历第 2 个字符时就能终止，避免继续构建整张表。代价是每处理一个字符都要多做一次比较，常数略大。两者渐近复杂度相同，面试中二者皆可，重点是要能讲清「两遍」与「单遍 + 提前终止」的差异。

解法三：定长 26 数组哈希表（最优实践）

思路

题目约束字符只可能是小写字母，因此可以用固定大小int[26]数组替代哈希表：count[c - 'a']即字符c的频率。数组下标运算比哈希函数更快、对 CPU 缓存更友好，且避免了哈希碰撞的开销。校验时采用递减法：直接用chars的频率数组逐个扣减单词字符，一旦某位置变成负数说明该单词非法；每个单词处理完后，用保存的原始副本org重置数组。

算法步骤

1. 创建长度 26 的数组count，遍历chars填充频率；
2. 复制一份count到org，用于每轮重置；
3. 对每个单词：
   • 逐字符执行count[c - 'a']--；
   • 若某次递减后为负数，标记非法并 break；
   • 若合法，累加len(w)到res；
   • 将count重置为org，供下一个单词使用；
4. 返回res。

多语言实现

class Solution: def countCharacters(self, words: List[str], chars: str) -> int: count = [0] * 26 for c in chars: count[ord(c) - ord('a')] += 1 org = count[:] res = 0 for w in words: good = True for c in w: i = ord(c) - ord('a') count[i] -= 1 if count[i] < 0: good = False break if good: res += len(w) for i in range(26): count[i] = org[i] return res

public class Solution { public int countCharacters(String[] words, String chars) { int[] count = new int[26]; for (char c : chars.toCharArray()) { count[c - 'a']++; } int[] org = count.clone(); int res = 0; for (String w : words) { boolean good = true; for (int i = 0; i < w.length(); i++) { int j = w.charAt(i) - 'a'; count[j]--; if (count[j] < 0) { good = false; break; } } if (good) { res += w.length(); } for (int i = 0; i < 26; i++) { count[i] = org[i]; } } return res; } }

class Solution { public: int countCharacters(vector<string>& words, string chars) { vector<int> count(26, 0); for (char c : chars) { count[c - 'a']++; } vector<int> org = count; int res = 0; for (string& w : words) { bool good = true; for (char& c : w) { int i = c - 'a'; count[i]--; if (count[i] < 0) { good = false; break; } } if (good) { res += w.length(); } for (int i = 0; i < 26; i++) { count[i] = org[i]; } } return res; } };

class Solution { /** * @param {string[]} words * @param {string} chars * @return {number} */ countCharacters(words, chars) { const count = new Array(26).fill(0); for (let c of chars) { count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++; } const org = [...count]; let res = 0; for (let w of words) { let good = true; for (let c of w) { const i = c.charCodeAt(0) - 'a'.charCodeAt(0); count[i]--; if (count[i] < 0) { good = false; break; } } if (good) { res += w.length; } for (let i = 0; i < 26; i++) { count[i] = org[i]; } } return res; } }

public class Solution { public int CountCharacters(string[] words, string chars) { int[] count = new int[26]; foreach (char c in chars) { count[c - 'a']++; } int[] org = (int[])count.Clone(); int res = 0; foreach (string w in words) { bool good = true; foreach (char c in w) { int i = c - 'a'; count[i]--; if (count[i] < 0) { good = false; break; } } if (good) { res += w.Length; } for (int i = 0; i < 26; i++) { count[i] = org[i]; } } return res; } }

func countCharacters(words []string, chars string) int { count := make([]int, 26) for _, c := range chars { count[c-'a']++ } org := make([]int, 26) copy(org, count) res := 0 for _, w := range words { good := true for _, c := range w { i := c - 'a' count[i]-- if count[i] < 0 { good = false break } } if good { res += len(w) } copy(count, org) } return res }

class Solution { fun countCharacters(words: Array<String>, chars: String): Int { val count = IntArray(26) for (c in chars) { count[c - 'a']++ } val org = count.copyOf() var res = 0 for (w in words) { var good = true for (c in w) { val i = c - 'a' count[i]-- if (count[i] < 0) { good = false break } } if (good) { res += w.length } for (i in 0 until 26) { count[i] = org[i] } } return res } }

class Solution { func countCharacters(_ words: [String], _ chars: String) -> Int { var count = Int let aValue = Int(Character("a").asciiValue!) for c in chars { count[Int(c.asciiValue!) - aValue] += 1 } let org = count var res = 0 for w in words { var good = true for c in w { let i = Int(c.asciiValue!) - aValue count[i] -= 1 if count[i] < 0 { good = false break } } if good { res += w.count } count = org } return res } }

impl Solution { pub fn count_characters(words: Vec<String>, chars: String) -> i32 { let mut count = [0i32; 26]; for c in chars.bytes() { count[(c - b'a') as usize] += 1; } let org = count; let mut res = 0; for w in &words { let mut good = true; for c in w.bytes() { let i = (c - b'a') as usize; count[i] -= 1; if count[i] < 0 { good = false; break; } } if good { res += w.len() as i32; } count = org; } res } }

复杂度分析

• 时间复杂度：O(n + m·k)，其中 n 为chars长度，m 为单词数，k 为单词平均长度；
• 空间复杂度：O(1)——固定 26 长度的数组，不随输入规模增长。

为什么数组版本更优

从实现层面看，数组方案有三点收益：

1. 无哈希开销：c - 'a'是纯算术运算，不涉及哈希函数计算与碰撞处理；
2. 缓存友好：26 个 int 完全驻留于 L1 缓存，访问模式是顺序或近似顺序的；
3. 代码意图清晰：count[c - 'a']--配合「小于 0 即非法」的判断，直观表达"消耗字符"的过程。

仓库的 Java 实现 提供了该思路的"直观版"：为每个单词单独建int[26]频率数组，再与chars的数组逐下标比较（arrS[i] > arrChars[i]即非法）。它没有使用递减 + 重置的技巧，但两者在复杂度上完全等价，适合作为最容易写对的第一版。Kotlin 版中则有IntArray.canMake的模块化写法，把「比较两个频率数组」抽成独立函数，增强了可读性。

常见误区

误区一：修改了原始的字符计数表却未恢复

逐词校验时，必须使用chars频率表的新鲜副本，或在校验后将其重置。常见错误是直接递减原始count却不恢复，导致后续单词可用的字符数被错误减少，输出偏小。解法三中用org副本每轮重置，正是为了避免这一点；如果采用"每个单词新建频率数组再比较"的方式（如仓库 Java 直观版），则天然规避该问题。

误区二：只检查字符"存在"而不检查"频率"

判断单词能否拼成时，只确认每个字符都出现在chars里是不够的，必须验证单词中每个字符的频率不超过chars中该字符的频率。例如chars = "ab"时，"aab"虽然每个字符都出现在chars中，但'a'需要 2 个而chars只有 1 个，因此"aab"无法拼成。

实战要点总结

三个解法的时间复杂度均为 O(n + m·k)。当题目明确限定字符集（如仅小写字母、仅数字）时，优先选用定长数组；当字符集未知或很大（如 Unicode）时，退回哈希表方案。本题的判定逻辑——逐字符频率比较——也是「Valid Anagram」「Ransom Note」等一批计数类题目的共同基础，掌握好数组与哈希表的互换，即可一通百通。

参考实现索引

• 本文对应题目详解：articles/find-words-that-can-be-formed-by-characters.md
• Java 实现（数组两遍比较版）：java/1160-find-words-that-can-be-formed-by-characters.java
• Kotlin 实现（含模块化与函数式短写三版）：kotlin/1160-find-words-that-can-be-formed-by-characters.kt
• 项目全局导航：README.md

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode