1002. 查找共用字符

🟢   🔖  数组 哈希表 字符串  🔗 力扣 LeetCode

题目

Given a string array words, return an array of all characters that show up in all strings within thewords (including duplicates). You may return the answer in any order.

Example 1:

Input: words = ["bella","label","roller"]

Output: ["e","l","l"]

Example 2:

Input: words = ["cool","lock","cook"]

Output: ["c","o"]

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.

题目大意

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符 ），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

输入： words = ["bella","label","roller"]

输出：["e","l","l"]

示例 2：

输入： words = ["cool","lock","cook"]

输出：["c","o"]

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 由小写英文字母组成

解题思路

每个字符串可以用一个长度为 26 的数组表示，记录每个字符的出现频率。 使用这些频率数组，求出所有字符串的字符频率的交集，即每个字符的最小频率。

1. 初始化一个数组 minFreq，长度为 26，初始值为 Infinity，表示每个字符的最小频率。
2. 遍历 words 中的每个字符串，计算它的字符频率。
3. 更新 minFreq，对于每个字符，取当前频率和最小频率的较小值。
4. 根据 minFreq 构造结果数组，如果某个字符在 minFreq 中的值为 k，则将该字符添加 k 次到结果数组。

复杂度分析

• 时间复杂度：O(n * m)

  • 遍历每个字符串的字符频率：O(n * m)，其中 n 是 words 的长度，m 是每个字符串的平均长度。
  • 遍历字符频率数组进行交集：O(26 * n)，常数时间复杂度。
  • 总时间复杂度为 O(n * m)。

• 空间复杂度：O(1)，使用了一个大小为 26 的数组 minFreq 和一个 freq 数组，空间复杂度为 O(26)，即 O(1)（常数空间）。

代码

/**
 * @param {string[]} words
 * @return {string[]}
 */
var commonChars = function (words) {
	const minFreq = new Array(26).fill(Infinity); // 初始化最小频率数组

	for (let word of words) {
		const freq = new Array(26).fill(0); // 当前单词的字符频率
		for (let char of word) {
			freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
		}
		for (let i = 0; i < 26; i++) {
			minFreq[i] = Math.min(minFreq[i], freq[i]); // 更新最小频率
		}
	}

	const res = [];
	for (let i = 0; i < 26; i++) {
		while (minFreq[i] > 0) {
			res.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
			minFreq[i]--;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
350	两个数组的交集 II	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗