跳至主要內容

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

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

🟢   🔖  哈希表 字符串 计数  🔗 力扣open in new window LeetCodeopen in new window

题目

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;
};
Copyright © 2024 2xiao