0893. Groups of Special-Equivalent Strings

题目信息

题号:

0893

难度:

Medium

主题:

字符串、奇偶下标、等价分组

原题:

LeetCode 0893

重点:

一次操作只能交换两个同为偶数或同为奇数的下标;能够通过任意多次操作互相变换的字符串属于同一等价组

题目重述

给定一组长度相同的小写字符串 words。对一个字符串可以重复执行特殊交换:选择两个下标,它们必须同为偶数或同为奇数,然后交换对应字符。下标从 0 开始。

若两个字符串能够通过零次或多次特殊交换互相变换,则它们特殊等价。特殊等价关系会把所有输入字符串划分为若干组。请返回不同特殊等价组的数量;重复字符串自然属于同一组。

1 <= words.length <= 1000,1 <= words[i].length <= 20,所有字符串长度相同且只包含小写英文字母。

自建示例

五字符字符串按奇偶位置分别重排:

输入:words = ["abcde","edcba","bbcde"]
输出:2
解释:abcde 的偶数下标字符为 a、c、e,奇数下标字符为 b、d;edcba 在两类下标中分别拥有相同字符集合,因此二者特殊等价。bbcde 的偶数下标字符为 b、c、e,与前两者不同,单独形成另一组。

单字符字符串不能执行交换:

输入:words = ["x","x","y"]
输出:2
解释:字符串长度为 1,没有两个同奇偶性的不同下标可交换。两个 x 属于同一组,y 属于另一组,因此共有两组。