Medium

题目描述

给你一个字符串数组 words，所有字符串长度相同。

在一次移动中，你可以交换字符串 words[i] 中任意两个偶数索引的字符，或者交换任意两个奇数索引的字符。

如果经过任意次数的移动后，words[i] == words[j]，那么两个字符串 words[i] 和 words[j] 是特殊等价的。

  • 例如，words[i] = "zzxy" 和 words[j] = "xyzz" 是特殊等价的，因为我们可以通过移动 "zzxy" -> "xzzy" -> "xyzz" 来实现。

来自 words 的特殊等价字符串组是一个非空的字符串子集，满足：

  • 该组中的每对字符串都是特殊等价的，并且
  • 该组是最大的（即，不存在一个不在该组中的字符串 words[i]，使得 words[i] 与该组中的每个字符串都特殊等价）。

返回 words 中特殊等价字符串组的数量。

示例 1：

输入：words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
输出：3
解释：
一组是 ["abcd", "cdab", "cbad"]，因为它们两两之间都是特殊等价的，且其他字符串都不与这些字符串特殊等价。
另外两组是 ["xyzz", "zzxy"] 和 ["zzyx"]。
特别注意，"zzxy" 与 "zzyx" 不是特殊等价的。

示例 2：

输入：words = ["abc","acb","bac","bca","cab","cba"]
输出：3

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 20
  • words[i] 由小写英文字母组成
  • 所有字符串的长度相同

解题思路

解题思路：

这道题的关键在于理解什么是"特殊等价"字符串。由于我们只能交换偶数索引位置的字符，或者交换奇数索引位置的字符，因此两个字符串特殊等价的充要条件是：

  1. 它们在偶数位置上的字符集合相同
  2. 它们在奇数位置上的字符集合相同

基于这个观察，我们可以为每个字符串构造一个标准形式（canonical form）：

  • 将偶数位置的字符排序后连接
  • 将奇数位置的字符排序后连接
  • 将两部分组合成一个唯一的标识符

如果两个字符串有相同的标准形式，那么它们就是特殊等价的。

算法步骤：

  1. 遍历每个字符串，分别提取偶数位置和奇数位置的字符
  2. 对这两部分字符分别排序
  3. 将排序后的偶数位置字符和奇数位置字符连接，形成该字符串的标准形式
  4. 使用哈希集合统计不同标准形式的数量，即为答案

时间复杂度： O(n * m log m)，其中 n 是字符串数量，m 是字符串长度 空间复杂度： O(n * m)，用于存储标准形式

代码实现

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        unordered_set<string> groups;
        
        for (const string& word : words) {
            string even = "", odd = "";
            
            // 分离偶数位置和奇数位置的字符
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    even += word[i];
                } else {
                    odd += word[i];
                }
            }
            
            // 对偶数位置和奇数位置的字符分别排序
            sort(even.begin(), even.end());
            sort(odd.begin(), odd.end());
            
            // 组合成标准形式
            groups.insert(even + "#" + odd);
        }
        
        return groups.size();
    }
};

class Solution:
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        groups = set()
        
        for word in words:
            even = []
            odd = []
            
            # 分离偶数位置和奇数位置的字符
            for i, char in enumerate(word):
                if i % 2 == 0:
                    even.append(char)
                else:
                    odd.append(char)
            
            # 对偶数位置和奇数位置的字符分别排序
            even.sort()
            odd.sort()
            
            # 组合成标准形式
            groups.add(''.join(even) + '#' + ''.join(odd))
        
        return len(groups)

public class Solution {
    public int NumSpecialEquivGroups(string[] words) {
        HashSet<string> groups = new HashSet<string>();
        
        foreach (string word in words) {
            List<char> even = new List<char>();
            List<char> odd = new List<char>();
            
            // 分离偶数位置和奇数位置的字符
            for (int i = 0; i < word.Length; i++) {
                if (i % 2 == 0) {
                    even.Add(word[i]);
                } else {
                    odd.Add(word[i]);
                }
            }
            
            // 对偶数位置和奇数位置的字符分别排序
            even.Sort();
            odd.Sort();
            
            // 组合成标准形式
            string canonical = new string(even.ToArray()) + "#" + new string(odd.ToArray());
            groups.Add(canonical);
        }
        
        return groups.Count;
    }
}

var numSpecialEquivGroups = function(words) {
    const normalize = (word) => {
        let even = [];
        let odd = [];
        
        for (let i = 0; i < word.length; i++) {
            if (i % 2 === 0) {
                even.push(word[i]);
            } else {
                odd.push(word[i]);
            }
        }
        
        even.sort();
        odd.sort();
        
        return even.join('') + '|' + odd.join('');
    };
    
    const groups = new Set();
    
    for (const word of words) {
        groups.add(normalize(word));
    }
    
    return groups.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × m log m)
空间复杂度O(n × m)

其中 n 是字符串数组的长度，m 是每个字符串的长度。时间复杂度主要来自于对每个字符串的偶数位置和奇数位置字符进行排序，空间复杂度主要用于存储哈希集合中的标准形式字符串。