strs = ["tars","rats","arts","star"]

LeetCode 839. 相似字符串组 题目描述 我们给定一个字符串列表 strs ，其中每个字符串的长度相同，并且是 字母异位词 （即组成字母相同，但排列可能不同）。 如果两个字符串 s1 和 s2 是相似的，则它们可以通过交换 一次 字符串中的两个字符（位置不同）而变得完全相同。 相似关系是传递的，例如：如果 "tars" 与 "rats" 相似， "rats" 与 "arts" 相似，那么 "tars" 、 "rats" 、 "arts" 属于同一个相似组。 要求计算输入列表中有多少个相似字符串组。 示例： "tars" 与 "rats" 相似（交换 't' 和 'r' 的位置可互换） "rats" 与 "arts" 相似 但 "tars" 与 "arts" 不直接相似（需要两次交换） 因为相似可传递，前三个字符串属于同一组 "star" 与它们都不相似，是另一组 结果：2 组。 解题思路 这道题本质是 求连通分量个数 。 将每个字符串看作图中的一个节点。 如果两个字符串相似，则在它们之间连一条边。 最后计算有多少个连通分量。 关键是如何判断“相似”： 如果两个字符串完全相同 → 相似（可视为交换 0 次）。 如果两个字符串长度相同，比较它们不同的字符位置： 如果不同位置的数量不是 2 → 不相似。 如果不同位置的数量是 2，并且交换这两个位置的字符后两字符串相等 → 相似。 详细步骤 步骤 1：判断两个字符串是否相似 遍历两个字符串，记录不同的字符位置索引。 如果不同的位置数量为 0 → 相似。 如果不同的位置数量为 2，设位置为 i 和 j，检查 s1[i] == s2[j] 且 s1[j] == s2[i] → 相似。 其他情况 → 不相似。 示例： "tars" 与 "rats" 比较： 索引 0: t ≠ r 索引 1: a = a 索引 2: r ≠ t 索引 3: s = s 不同位置：[ 0, 2 ] 交换 s1 的 0 和 2 位置：t ↔ r → 得到 "rats" ，与 s2 相同 → 相似。 步骤 2：建图 图的节点数量 = 字符串数量 n。 遍历所有字符串对 (i, j)，如果相似，则添加一条无向边。 步骤 3：求连通分量数量 可以用并查集（Union-Find）实现： 初始化每个节点的父节点为自身。 遍历所有字符串对，如果相似，合并它们所在的集合。 最后统计有多少个不同的根节点（即不同的集合）。 步骤 4：并查集实现细节 合并时按秩合并（或简单按大小/深度优化）。 查找时路径压缩。 举例推导 输入： strs = ["tars","rats","arts","star"] n = 4，并查集初始：{0}, {1}, {2}, {3} 比较 (0,1)： "tars" 与 "rats" → 相似 → 合并 0 和 1 → 集合 {0,1}, {2}, {3} 比较 (0,2)： "tars" 与 "arts" → 不相似（不同位置数量为 3）→ 不合并 比较 (0,3)： "tars" 与 "star" → 不相似（不同位置数量为 4）→ 不合并 比较 (1,2)： "rats" 与 "arts" → 相似 → 合并 1 和 2，但 1 的根是 0，所以合并 0 和 2 → 集合 {0,1,2}, {3} 比较 (1,3)：不相似 比较 (2,3)：不相似 最终并查集根：0 和 3 → 2 个连通分量 → 答案 2。 复杂度分析 判断相似：O(L)，L 是字符串长度。 遍历所有字符串对：O(n²) 次比较。 总时间复杂度：O(n² * L)。 空间复杂度：O(n) 用于并查集。 总结 这道题是将字符串相似关系转化为图连通性问题，并用并查集高效求解连通分量个数，关键在于正确实现“一次交换可相同”的相似判断逻辑。