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

给你一个字符串数组 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] 由小写英文字母组成

方法一：统计每种字符的频数

思路与算法

我们可以任意进行移动字符的操作。因此，假设 words 的长度为 n，我们只需要使得每种字符的总出现次数能够被 n 整除，即可以存在一种操作，使得操作后所有字符串均相等。

我们用 cnt 数组维护每种字符的频数。由于每个字符串 words}[i] 仅由小写英文字母组成，因此我们将 cnt 的长度设为对应字符集的大小 |\Sigma| = 26。同时，cnt}[k] 对应字典序第 k 个字符的频数。

为了判断是否可行，我们遍历 words 中的每个字符串统计每种字符的频数，并最终判断它们是否均可以被 n 整除。

代码

[sol1-C++]

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        vector<int> cnt(26, 0);   // 每种字符的频数
        int n = words.size();
        for (const string& wd: words){
            for (char ch: wd){
                ++cnt[ch-'a'];
            }
        }
        return all_of(cnt.begin(), cnt.end(), [n](int x){ return x % n == 0; });
    }
};

[sol1-Python3]

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        cnt = [0] * 26   # 每种字符的频数
        n = len(words)
        for wd in words:
            for ch in wd:
                cnt[ord(ch)-ord('a')] += 1
        return all(k % n == 0 for k in cnt)

复杂度分析

• 时间复杂度：O(m + |\Sigma|)，其中 m 为 words 中所有字符串的长度总和，|\Sigma| 为字符集的大小，本题中即为所有小写英文字符的数量。初始化 cnt 数组的时间复杂度为 O(|\Sigma|)，遍历统计每个字符数量的时间复杂度为 O(m)，判断整除的时间复杂度为 O(|\Sigma|)。

• 空间复杂度：O(|\Sigma|)，即为 cnt 数组的大小。