Easy

题目描述

给你一个字符串数组 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. 统计总字符频次：遍历所有字符串，统计每个字符在整个数组中出现的总次数。

  2. 检查整除性：要使所有字符串相等，每个字符的总出现次数必须能被字符串数量整除。这是因为如果最终所有字符串都相等，那么每个字符串中该字符的数量应该相同。

  3. 验证可行性：如果所有字符的出现次数都能被字符串数量整除，则返回 true；否则返回 false。

举例分析：

  • 对于 ["abc","aabc","bc"]，字符统计为：a:2, b:3, c:3，字符串数量为3
  • 2%3≠0，3%3=0，3%3=0，由于字符’a’无法平均分配，看起来应该返回false
  • 但实际上可以重新分配：每个字符串最终都是"abc"，需要a:3, b:3, c:3，而我们总共有a:2, b:3, c:3，所以无法实现

重新分析：要让3个字符串相等，每个字符在每个字符串中的出现次数必须相同，因此每个字符的总次数必须是字符串数量的倍数。

代码实现

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        unordered_map<char, int> count;
        
        // 统计所有字符的总出现次数
        for (const string& word : words) {
            for (char c : word) {
                count[c]++;
            }
        }
        
        int n = words.size();
        
        // 检查每个字符的出现次数是否能被字符串数量整除
        for (const auto& pair : count) {
            if (pair.second % n != 0) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        from collections import Counter
        
        # 统计所有字符的总出现次数
        count = Counter()
        for word in words:
            count.update(word)
        
        n = len(words)
        
        # 检查每个字符的出现次数是否能被字符串数量整除
        for freq in count.values():
            if freq % n != 0:
                return False
        
        return True

public class Solution {
    public bool MakeEqual(string[] words) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        
        // 统计所有字符的总出现次数
        foreach (string word in words) {
            foreach (char c in word) {
                if (count.ContainsKey(c)) {
                    count[c]++;
                } else {
                    count[c] = 1;
                }
            }
        }
        
        int n = words.Length;
        
        // 检查每个字符的出现次数是否能被字符串数量整除
        foreach (int freq in count.Values) {
            if (freq % n != 0) {
                return false;
            }
        }
        
        return true;
    }
}

/**
 * @param {string[]} words
 * @return {boolean}
 */
var makeEqual = function(words) {
    const count = new Map();
    
    // 统计所有字符的总出现次数
    for (const word of words) {
        for (const char of word) {
            count.set(char, (count.get(char) || 0) + 1);
        }
    }
    
    const n = words.length;
    
    // 检查每个字符的出现次数是否能被字符串数量整除
    for (const freq of count.values()) {
        if (freq % n !== 0) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N)其中N是所有字符串中字符的总数，需要遍历每个字符一次
空间复杂度O(1)哈希表最多存储26个小写字母，为常数空间