Hard

题目描述

如果两个字符串 X 和 Y 满足以下条件之一，我们就认为它们是相似的：

  • 它们是相同的，或者
  • 我们可以通过交换字符串 X 中最多两个字母（在不同位置）使它们相等。

例如，“tars” 和 “rats” 相似（交换位置 0 和 2），“rats” 和 “arts” 相似，但 “star” 与 “tars”、“rats” 或 “arts” 都不相似。

它们一起形成了两个相似性连通分组：{“tars”, “rats”, “arts”} 和 {“star”}。请注意，“tars” 和 “arts” 在同一组中，尽管它们不直接相似。形式上，每个组都是这样的：当且仅当一个单词与该组中至少一个其他单词相似时，该单词才在该组中。

给你一个字符串列表 strs，其中 strs 中的每个字符串都是 strs 中每个其他字符串的字母异位词。请问有多少个组？

示例 1：

输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：

输入：strs = ["omv","ovm"]
输出：1

提示：

  • 1 <= strs.length <= 300
  • 1 <= strs[i].length <= 300
  • strs[i] 仅由小写字母组成
  • strs 中的所有单词都具有相同的长度并且是彼此的字母异位词

解题思路

解题思路

这是一个图论中的连通分量问题。我们需要找出有多少个相似字符串的连通组。

核心思路：

  1. 首先定义相似性：两个字符串相似当且仅当它们完全相同，或者可以通过交换最多两个位置的字符使它们相同
  2. 将字符串看作图中的节点，相似的字符串之间连边
  3. 问题转化为求图中连通分量的个数

判断相似性的方法：

  • 如果两个字符串相同，则相似
  • 如果两个字符串不同，统计不同位置的个数：
    • 如果恰好有2个不同位置，且交换后能相等，则相似
    • 否则不相似

解法选择：

  1. 并查集（推荐）：适合处理动态连通性问题，代码简洁
  2. DFS/BFS：从每个未访问的节点开始遍历整个连通分量
  3. 图的邻接表 + 连通分量计数

由于字符串数量不大（最多300），三种方法的时间复杂度差异不大，这里选择并查集作为主要解法，因为它更直观地表达了"分组"的概念。

时间复杂度主要来自于两两比较字符串的相似性，为 O(n²×m)，其中 n 是字符串数量，m 是字符串长度。

代码实现

class Solution {
public:
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        vector<int> parent(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parent[x] = y;
            }
        };
        
        auto isSimilar = [&](const string& a, const string& b) {
            if (a == b) return true;
            vector<int> diff;
            for (int i = 0; i < a.length(); i++) {
                if (a[i] != b[i]) {
                    diff.push_back(i);
                }
            }
            return diff.size() == 2 && a[diff[0]] == b[diff[1]] && a[diff[1]] == b[diff[0]];
        };
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    unite(i, j);
                }
            }
        }
        
        int groups = 0;
        for (int i = 0; i < n; i++) {
            if (find(i) == i) {
                groups++;
            }
        }
        
        return groups;
    }
};

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        n = len(strs)
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        def is_similar(a, b):
            if a == b:
                return True
            diff = []
            for i in range(len(a)):
                if a[i] != b[i]:
                    diff.append(i)
            return len(diff) == 2 and a[diff[0]] == b[diff[1]] and a[diff[1]] == b[diff[0]]
        
        for i in range(n):
            for j in range(i + 1, n):
                if is_similar(strs[i], strs[j]):
                    unite(i, j)
        
        return sum(1 for i in range(n) if find(i) == i)

public class Solution {
    public int NumSimilarGroups(string[] strs) {
        int n = strs.Length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        void Unite(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px != py) {
                parent[px] = py;
            }
        }
        
        bool IsSimilar(string a, string b) {
            if (a == b) return true;
            var diff = new List<int>();
            for (int i = 0; i < a.Length; i++) {
                if (a[i] != b[i]) {
                    diff.Add(i);
                }
            }
            return diff.Count == 2 && a[diff[0]] == b[diff[1]] && a[diff[1]] == b[diff[0]];
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (IsSimilar(strs[i], strs[j])) {
                    Unite(i, j);
                }
            }
        }
        
        int groups = 0;
        for (int i = 0; i < n; i++) {
            if (Find(i) == i) {
                groups++;
            }
        }
        
        return groups;
    }
}

var numSimilarGroups = function(strs) {
    const n = strs.length;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        return parent[x]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²×m×α(n))
空间复杂度O(n)

其中 n 是字符串数量，m 是字符串长度，α(n) 是阿克曼函数的反函数（并查集操作的均摊复杂度）。实际上由于 α(n) 在实际应用中可视为常数，时间复杂度可近似为 O(n²×m)。

相关题目