0839. Similar String Groups

题目信息

题号:

0839

难度:

Hard

主题:

字符串、交换关系、连通分组

原题:

LeetCode 0839

重点:

两字符串相同或可通过交换其中一个字符串的两个位置变成相同即直接相似;分组按相似关系的传递连通性确定

题目重述

给定字符串数组 strs,所有字符串长度相同,并且彼此都是字母异位词。若两个字符串完全相同,或者能在其中一个字符串中交换至多一对不同位置的字符后得到另一个字符串,则它们直接相似。

把每个字符串实例视为一个节点,直接相似的两个实例之间相连。即使两个字符串不直接相似,只要能通过一系列直接相似的字符串相互到达,它们也属于同一组。请返回最终的连通组数量。

1 <= strs.length <= 300,每个字符串长度在 [1, 300] 范围内,只包含小写英文字母;所有字符串长度相同且互为字母异位词。

自建示例

传递相似与独立字符串形成两个组:

输入:strs = ["abcd","bacd","bcad","cdab"]
输出:2
解释:"abcd" 交换下标 0、1 可得到 "bacd","bacd" 再交换下标 1、2 可得到 "bcad",因此前三个字符串通过传递关系属于同一组;"cdab" 与前三者均不能通过一次交换直接相似,也没有中间字符串连接,单独形成第二组。

数组只有一个字符串:

输入:strs = ["aa"]
输出:1
解释:数组长度达到题目允许的最小值,唯一字符串自身构成一个相似组。