0893. 特殊等价字符串组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 哈希

1. 📝 题目描述

• leetcode

给你一个字符串数组 words。

一步操作中，你可以交换字符串 words[i] 的任意两个偶数下标对应的字符或任意两个奇数下标对应的字符。

对两个字符串 words[i] 和 words[j] 而言，如果经过任意次数的操作，words[i] == words[j]，那么这两个字符串是 特殊等价 的。

• 例如，words[i] = "zzxy" 和 words[j] = "xyzz" 是一对 特殊等价 字符串，因为可以按 "zzxy" -> "xzzy" -> "xyzz" 的操作路径使 words[i] == words[j]。

现在规定，words 的 一组特殊等价字符串 就是 words 的一个同时满足下述条件的非空子集：

• 该组中的每一对字符串都是 特殊等价 的
• 该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值（也就是说，如果一个字符串不在该组中，那么这个字符串就 不会 与该组内任何字符串特殊等价）

返回 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
解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]

---

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 20
• 所有 words[i] 都只由小写字母组成。
• 所有 words[i] 都具有相同的长度。

2. 🎯 s.1 - 排序 + 哈希

c

int cmpChar(const void* a, const void* b) { return *(char*)a - *(char*)b; }

int numSpecialEquivGroups(char** words, int wordsSize) {
    char sigs[wordsSize][101];
    for (int i = 0; i < wordsSize; i++) {
        int n = strlen(words[i]);
        char even[51], odd[51];
        int eLen = 0, oLen = 0;
        for (int j = 0; j < n; j++) {
            if (j % 2 == 0) even[eLen++] = words[i][j];
            else odd[oLen++] = words[i][j];
        }
        qsort(even, eLen, sizeof(char), cmpChar);
        qsort(odd, oLen, sizeof(char), cmpChar);
        even[eLen] = '\0'; odd[oLen] = '\0';
        sprintf(sigs[i], "%s|%s", even, odd);
    }
    int res = 0;
    for (int i = 0; i < wordsSize; i++) {
        bool dup = false;
        for (int j = 0; j < i; j++)
            if (strcmp(sigs[i], sigs[j]) == 0) { dup = true; break; }
        if (!dup) res++;
    }
    return res;
}

js

/**
 * @param {string[]} words
 * @return {number}
 */
var numSpecialEquivGroups = function (words) {
  const set = new Set()
  for (const word of words) {
    const even = [],
      odd = []
    for (let i = 0; i < word.length; i++) {
      if (i % 2 === 0) even.push(word[i])
      else odd.push(word[i])
    }
    set.add(even.sort().join('') + odd.sort().join(''))
  }
  return set.size
}

py

class Solution:
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        return len({
            tuple(sorted(w[::2])) + tuple(sorted(w[1::2]))
            for w in words
        })

• 时间复杂度：$O(n\times m\log m)$，其中 n 是单词数，m 是单词长度
• 空间复杂度：$O(n\times m)$

算法思路：

• 将每个单词的偶数位和奇数位字符分别排序，拼接为特征串
• 用集合统计不同的特征串数量