1897.md

title	description	keywords
1897. 重新分配字符使所有字符串都相等	LeetCode 1897. 重新分配字符使所有字符串都相等题解，Redistribute Characters to Make All Strings Equal，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1897. 重新分配字符使所有字符串都相等 重新分配字符使所有字符串都相等 Redistribute Characters to Make All Strings Equal 解题思路 哈希表 字符串 计数

1897. 重新分配字符使所有字符串都相等

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

题目

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true _if you can makeevery string in _words equal using any number of operations,andfalse otherwise.

Example 1:

Input: words = ["abc","aabc","bc"]

Output: true

Explanation: Move the first 'a' in words[1] to the front of words[2],

to make words[1] = "abc" and words[2] = "abc".

All the strings are now equal to "abc", so return true.

Example 2:

Input: words = ["ab","a"]

Output: false

Explanation: It is impossible to make all the strings equal using the operation.

Constraints:

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

题目大意

给你一个字符串数组 words（下标 从 0 开始 计数）。

在一步操作中，需先选出两个 不同 下标 i 和 j，其中 words[i] 是一个非空字符串，接着将 words[i] 中的 任一 字符移动到 words[j] 中的 任一 位置上。

如果执行任意步操作可以使 words 中的每个字符串都相等，返回 true ；否则，返回 false 。

示例 1：

输入： words = ["abc","aabc","bc"]

输出： true

解释： 将 words[1] 中的第一个 'a' 移动到 words[2] 的最前面。

使 words[1] = "abc" 且 words[2] = "abc" 。

所有字符串都等于 "abc" ，所以返回 true 。

示例 2：

输入： words = ["ab","a"]

输出： false

解释： 执行操作无法使所有字符串都相等。

提示：

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

解题思路

1. 统计字符频率

   由于输入中的字符是小写英文字母（固定 26 个），可以用一个长度为 26 的数组 freq 来统计每个字符出现的总频率：

   • 将字符的 ASCII 值减去 'a' 的 ASCII 值得到其索引，例如 'a' 的索引为 0，'b' 的索引为 1，依此类推。
   • 遍历所有单词，更新数组中相应索引的频率值。

2. 检查频率是否满足条件

   将统计好的频率数组逐一检查：

   • 如果某个字符的总频率不能被单词的总数 n 整除，则说明这些字符无法均分到每个单词，直接返回 false。
   • 如果所有字符的频率都能被 n 整除，则返回 true。

复杂度分析

• 时间复杂度：O(k * m)
  • 遍历所有单词统计字符频率：O(k * m)，其中 k 是单词数，m 是平均单词长度。
  • 检查频率是否满足条件：固定长度 26，时间复杂度为 O(1)。
• 空间复杂度：O(1)，使用了长度为 26 的数组存储字符频率。

代码

/**
 * @param {string[]} words
 * @return {boolean}
 */
var makeEqual = function (words) {
	const n = words.length;
	const freq = new Array(26).fill(0); // 用长度为 26 的数组代替 Map

	// 统计所有单词中每个字符的出现频率
	for (let word of words) {
		for (let char of word) {
			freq[char.charCodeAt() - 97]++;
		}
	}

	// 检查所有字符的频率是否都能被 n 整除
	for (let count of freq) {
		if (count % n !== 0) {
			return false;
		}
	}
	return true;
};