特殊等价字符串组 图解题解

只能同奇偶换字符，求分成几组

给一个字符串数组 words，每个串等长。允许的操作只有两种：把某个串里两个偶数下标处的字符对调，或两个奇数下标处的对调。两个串若能靠这些操作变得完全一样，就叫特殊等价。按这层关系分组，返回组数。题面例子 words=["abcd","cdab","cbad","xyzz","zzxy","zzyx"] 的答案是 3。

整串排序当签名，会把两组并成一组

判两串等不等价，很容易想到把整串字符排序，排完一样就归一组，这会把不该并的串并到一起。拿 ab 和 ba：整串排序都得 ab，看着一组；可 a 在偶数下标、b 在奇数下标，把 ab 挪成 ba 要让偶数位 a 和奇数位 b 对调，属跨奇偶交换，题目不许，它们其实是两组。整串排序默认任意两字符都能换，比题目宽，才会误判。

偶数位排序加奇数位排序，就是签名

操作只发生在同奇偶位之间，所以不管怎么换，一个串偶数下标上那堆字符的构成永远不变，奇数下标上那堆也不变。这里的构成指多重集，也就是只数每种字母各出现几次、不看排列顺序。于是两串特殊等价，当且仅当偶数位、奇数位的字符多重集分别相同。

要给每个串造个能比对的代表，就把偶数位字符单独排序、奇数位字符单独排序，偶在前奇在后接成一个字符串，这就是签名，也就是把所有互相等价的串映成同一个字符串、方便去重。签名相同即特殊等价，不同即不等价。

每串现算签名，扔进集合数一数

遍历每个串，按下标奇偶拆成两组。下标从 0 起数，0 是偶数位，于是下标 0、2、4… 归偶数位那组，1、3、5… 归奇数位那组。两组各自排序，偶在前奇在后拼成签名，塞进哈希集合。所有串走完，集合自动合掉重复签名，剩几个不同签名就是几组，返回集合大小。

六个串逐个算签名，落到 3 组

拿题面的 words=["abcd","cdab","cbad","xyzz","zzxy","zzyx"] 手算。abcd 偶数位 a、c 排成 ac，奇数位 b、d 排成 bd，签名 acbd。cdab 偶数位 c、a 也排成 ac，奇数位 d、b 也排成 bd，签名同为 acbd。cbad 同理得 acbd，前三个并成一组。

接着 xyzz 偶数位 x、z 排成 xz，奇数位 y、z 排成 yz，签名 xzyz；zzxy 偶数位 z、x 得 xz，奇数位 z、y 得 yz，签名同样 xzyz，和 xyzz 并一组。最后 zzyx 偶数位 z、y 排成 yz，奇数位 z、x 排成 xz，签名 yzxz，跟前面都不同，自己一组。集合留下 acbd、xzyz、yzxz 三个，答案 3。

L log L 排序 n 次，ab 和 ba 为何分家

设 n 个串、每串长 L。每串把两半排序，代价 L·log L，合起来 O(n·L log L)；集合最多存 n 个签名、每个长 L，空间 O(n·L)。

两个本来相同的串签名一致，并进同一组。ab 和 ba 字母虽一样，a、b 分处偶奇两位、跨位换不动，签名一个 ab 一个 ba，判成两组，整串排序正会栽在这。长度不同的两串更省事，操作改不了长度，签名长度也不同，必然分开，无需特判。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        s = {''.join(sorted(word[::2]) + sorted(word[1::2])) for word in words}
        return len(s)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        unordered_set<string> s;
        for (auto& word : words) {
            string a = "", b = "";
            for (int i = 0; i < word.size(); ++i) {
                if (i & 1)
                    a += word[i];
                else
                    b += word[i];
            }
            sort(a.begin(), a.end());
            sort(b.begin(), b.end());
            s.insert(a + b);
        }
        return s.size();
    }
};

Java

import java.util.*;
class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> s = new HashSet<>();
        for (String word : words) {
            s.add(convert(word));
        }
        return s.size();
    }

    private String convert(String word) {
        List<Character> a = new ArrayList<>();
        List<Character> b = new ArrayList<>();
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (i % 2 == 0) {
                a.add(ch);
            } else {
                b.add(ch);
            }
        }
        Collections.sort(a);
        Collections.sort(b);
        StringBuilder sb = new StringBuilder();
        for (char c : a) {
            sb.append(c);
        }
        for (char c : b) {
            sb.append(c);
        }
        return sb.toString();
    }
}