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

这道题到底在问什么

输入

words=["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

输出

3

输入

words=["abc","acb","bac","bca","cab","cba"]

输出

3

最优解：一步一步想明白

1. 3记住这把钥匙：签名 = 排序后的偶数位 加 排序后的奇数位。下面每个串都现算它的签名，再看集合里有没有见过。
2. 4先把 4 个串摆出来。我们要逐个算签名、放进集合。集合现在是空的，0 组。
3. 5处理「abcd」。先看偶数下标 0 和 2，绿色这两个字符是 a 和 c，奇数位先灰着不动。
4. 6把偶数位的 a、c 排个序，得到 ac。这就是签名的前半截，顺序固定下来了。
5. 7再看奇数下标 1 和 3，绿色换到这两个字符 b 和 d，偶数位这回灰掉。
6. 8奇数位的 b、d 排序得 bd。前半 ac 接上后半 bd，「abcd」的签名就是 ac·bd。
7. 9拿 ac·bd 去集合里查，没见过，于是加进去，组数变成 1。
8. 10处理「cdab」。先看偶数下标 0 和 2，绿色这两个字符是 c 和 a，奇数位先灰着不动。
9. 11把偶数位的 c、a 排个序，得到 ac。这就是签名的前半截，顺序固定下来了。
10. 12再看奇数下标 1 和 3，绿色换到这两个字符 d 和 b，偶数位这回灰掉。
11. 13奇数位的 d、b 排序得 bd。前半 ac 接上后半 bd，「cdab」的签名就是 ac·bd。
12. 14拿 ac·bd 去集合里查，发现第 1 组里已有同款签名，「cdab」和它们特殊等价，并进去，组数不变还是 1。
13. 15处理「xyzz」。先看偶数下标 0 和 2，绿色这两个字符是 x 和 z，奇数位先灰着不动。
14. 16把偶数位的 x、z 排个序，得到 xz。这就是签名的前半截，顺序固定下来了。
15. 17再看奇数下标 1 和 3，绿色换到这两个字符 y 和 z，偶数位这回灰掉。
16. 18奇数位的 y、z 排序得 yz。前半 xz 接上后半 yz，「xyzz」的签名就是 xz·yz。
17. 19拿 xz·yz 去集合里查，没见过，于是加进去，组数变成 2。
18. 20处理「zzyx」。先看偶数下标 0 和 2，绿色这两个字符是 z 和 y，奇数位先灰着不动。
19. 21把偶数位的 z、y 排个序，得到 yz。这就是签名的前半截，顺序固定下来了。
20. 22再看奇数下标 1 和 3，绿色换到这两个字符 z 和 x，偶数位这回灰掉。
21. 23奇数位的 z、x 排序得 xz。前半 yz 接上后半 xz，「zzyx」的签名就是 yz·xz。
22. 24拿 yz·xz 去集合里查，没见过，于是加进去，组数变成 3。
23. 254 个串算完，集合里留下 3 个不同签名。abcd 和 cdab 撞同一个签名归一组，xyzz 和 zzyx 各自单独一组（注意 xyzz 与 zzyx 并不等价），最终 3 组。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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();
    }
};

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();
    }
}

复杂度

面试官可能追问