2157. 字符串分组

Hard

题目描述

给你一个下标从 0 开始的字符串数组 words。每个字符串都只包含 小写英文字母。words 中任一字符串里字母不会重复。

如果我们可以通过以下操作之一，从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 相连的 ：

往 s1 的字母集合中添加一个字母。
从 s1 的字母集合中删去一个字母。
将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

数组 words 可以分为一个或者多个无交集的组。如果一个字符串与另一个字符串相连，那么它们应该属于同一个组。

注意，你需要确保分组后，一个组里的任一字符串都不会与其他组的字符串相连。可以证明在这个条件下，分组方案是唯一的。

请你返回一个长度为 2 的数组 ans：

ans[0] 是 words 分组后的 总组数。
ans[1] 是字符串数目最多的组的大小。

示例 1：

输入：words = ["a","b","ab","cde"]
输出：[2,3]
解释：
- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 相连。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 相连。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 相连。
- words[3] 与其他字符串都不相连。
所以，words 可以分为 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。

示例 2：

输入：words = ["a","ab","abc"]
输出：[1,3]
解释：
- words[0] 与 words[1] 相连。
- words[1] 与 words[0] 和 words[2] 相连。
- words[2] 与 words[1] 相连。
因为所有字符串与其他字符串都相连，所以它们全部在同一个组内。
所以最大的组大小为 3 。

提示：

1 <= words.length <= 2 * 10^4
1 <= words[i].length <= 26
words[i] 只包含小写英文字母
words[i] 中每个字母最多出现一次

解题思路

这是一个图论连通性问题。我们需要建立字符串之间的连接关系，然后找到连通分量的数量和最大连通分量的大小。

核心思路：

位掩码表示字符集合：由于每个字符串中的字母不重复且只包含小写字母，我们可以用一个整数的位掩码来表示字符串的字母集合。例如，“ab” 可以表示为二进制 11（第0位和第1位为1）。
建立连接关系：两个字符串相连的条件是通过添加、删除或替换一个字母可以互相转换。对于位掩码来说：
- 添加一个字母：mask2 = mask1 | (1 << i)，其中i是新添加字母的位置
- 删除一个字母：mask2 = mask1 ^ (1 << i)，其中i是要删除字母的位置
- 替换一个字母：先删除一个字母，再添加一个字母
并查集求解：使用并查集来维护连通分量，统计分量数量和最大分量大小。

优化策略：

使用哈希表存储位掩码到字符串索引的映射，避免重复计算
对于每个字符串，只需要枚举26个可能的添加/删除/替换操作
通过位运算快速判断两个字符串是否相连

时间复杂度分析： 每个字符串最多产生 O(26) 个相邻状态，总体复杂度为 O(n × 26 × α(n))，其中α是反阿克曼函数。

代码实现

class Solution {
public:
    vector<int> groupStrings(vector<string>& words) {
        int n = words.size();
        unordered_map<int, int> maskToIndex;
        vector<int> parent(n), size(n, 1);
        
        // 初始化并查集
        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[y] = x;
                size[x] += size[y];
            }
        };
        
        // 将字符串转换为位掩码并建立映射
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i]) {
                mask |= (1 << (c - 'a'));
            }
            maskToIndex[mask] = i;
        }
        
        // 对每个字符串，尝试所有可能的连接
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i]) {
                mask |= (1 << (c - 'a'));
            }
            
            // 尝试删除一个字母
            for (int j = 0; j < 26; j++) {
                if (mask & (1 << j)) {
                    int newMask = mask ^ (1 << j);
                    if (maskToIndex.count(newMask)) {
                        unite(i, maskToIndex[newMask]);
                    }
                }
            }
            
            // 尝试添加一个字母
            for (int j = 0; j < 26; j++) {
                if (!(mask & (1 << j))) {
                    int newMask = mask | (1 << j);
                    if (maskToIndex.count(newMask)) {
                        unite(i, maskToIndex[newMask]);
                    }
                }
            }
            
            // 尝试替换一个字母
            for (int j = 0; j < 26; j++) {
                if (mask & (1 << j)) {
                    for (int k = 0; k < 26; k++) {
                        if (!(mask & (1 << k))) {
                            int newMask = (mask ^ (1 << j)) | (1 << k);
                            if (maskToIndex.count(newMask)) {
                                unite(i, maskToIndex[newMask]);
                            }
                        }
                    }
                }
            }
        }
        
        // 统计连通分量
        int groups = 0, maxSize = 0;
        for (int i = 0; i < n; i++) {
            if (find(i) == i) {
                groups++;
                maxSize = max(maxSize, size[i]);
            }
        }
        
        return {groups, maxSize};
    }
};

class Solution:
    def groupStrings(self, words: List[str]) -> List[int]:
        n = len(words)
        parent = list(range(n))
        size = [1] * 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[py] = px
                size[px] += size[py]
        
        # 将字符串转换为位掩码并建立映射
        mask_to_index = {}
        for i, word in enumerate(words):
            mask = 0
            for c in word:
                mask |= (1 << (ord(c) - ord('a')))
            mask_to_index[mask] = i
        
        # 对每个字符串，尝试所有可能的连接
        for i, word in enumerate(words):
            mask = 0
            for c in word:
                mask |= (1 << (ord(c) - ord('a')))
            
            # 尝试删除一个字母
            for j in range(26):
                if mask & (1 << j):
                    new_mask = mask ^ (1 << j)
                    if new_mask in mask_to_index:
                        unite(i, mask_to_index[new_mask])
            
            # 尝试添加一个字母
            for j in range(26):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    if new_mask in mask_to_index:
                        unite(i, mask_to_index[new_mask])
            
            # 尝试替换一个字母
            for j in range(26):
                if mask & (1 << j):
                    for k in range(26):
                        if not (mask & (1 << k)):
                            new_mask = (mask ^ (1 << j)) | (1 << k)
                            if new_mask in mask_to_index:
                                unite(i, mask_to_index[new_mask])
        
        # 统计连通分量
        groups = 0
        max_size = 0
        for i in range(n):
            if find(i) == i:
                groups += 1
                max_size = max(max_size, size[i])
        
        return [groups, max_size]

public class Solution {
    public int[] GroupStrings(string[] words) {
        int n = words.Length;
        int[] parent = new int[n];
        int[] size = new int[n];
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        
        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[py] = px;
                size[px] += size[py];
            }
        }
        
        // 将字符串转换为位掩码并建立映射
        var maskToIndex = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            int mask = 0;
            foreach (char c in words[i]) {
                mask |= (1 << (c - 'a'));
            }
            maskToIndex[mask] = i;
        }
        
        // 对每个字符串，尝试所有可能的连接
        for (int i = 0; i < n; i++) {
            int mask = 0;
            foreach (char c in words[i]) {
                mask |= (1 << (c - 'a'));
            }
            
            // 尝试删除一个字母
            for (int j = 0; j < 26; j++) {
                if ((mask & (1 << j)) != 0) {
                    int newMask = mask ^ (1 << j);
                    if (maskToIndex.ContainsKey(newMask)) {
                        Unite(i, maskToIndex[newMask]);
                    }
                }
            }
            
            // 尝试添加一个字母
            for (int j = 0; j < 26; j++) {
                if ((mask & (1 << j)) == 0) {
                    int newMask = mask | (1 << j);
                    if (maskToIndex.ContainsKey(newMask)) {
                        Unite(i, maskToIndex[newMask]);
                    }
                }
            }
            
            // 尝试替换一个字母
            for (int j = 0; j < 26; j++) {
                if ((mask & (1 << j)) != 0) {
                    for (int k = 0; k < 26; k++) {
                        if ((mask & (1 << k)) == 0) {
                            int newMask = (mask ^ (1 << j)) | (1 << k);
                            if (maskToIndex.ContainsKey(newMask)) {
                                Unite(i, maskToIndex[newMask]);
                            }
                        }
                    }
                }
            }
        }
        
        // 统计连通分量
        int groups = 0, maxSize = 0;
        for (int i = 0; i < n; i++) {
            if (Find(i) == i) {
                groups++;
                maxSize = Math.Max(maxSize, size[i]);
            }
        }
        
        return new int[] {groups, maxSize};
    }
}

var groupStrings = function(words) {
    const parent = new Map();
    const size = new Map();
    
    function find(x) {
        if (!parent.has(x)) {
            parent.set(x, x);
            size.set(x, 1);
        }
        if (parent.get(x) !== x) {
            parent.set(x, find(parent.get(x)));
        }
        return parent.get(x);
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px !== py) {
            if (size.get(px) < size.get(py)) {
                parent.set(px, py);
                size.set(py, size.get(py) + size.get(px));
            } else {
                parent.set(py, px);
                size.set(px, size.get(px) + size.get(py));
            }
        }
    }
    
    function stringToBitmask(word) {
        let mask = 0;
        for (let char of word) {
            mask |= (1 << (char.charCodeAt(0) - 97));
        }
        return mask;
    }
    
    const masks = words.map(stringToBitmask);
    const maskToIndex = new Map();
    
    for (let i = 0; i < masks.length; i++) {
        if (!maskToIndex.has(masks[i])) {
            maskToIndex.set(masks[i], []);
        }
        maskToIndex.get(masks[i]).push(i);
    }
    
    // Union words with same bitmask
    for (let indices of maskToIndex.values()) {
        for (let i = 1; i < indices.length; i++) {
            union(indices[0], indices[i]);
        }
    }
    
    const processedPairs = new Set();
    
    for (let i = 0; i < masks.length; i++) {
        const mask = masks[i];
        
        // Adding one letter
        for (let bit = 0; bit < 26; bit++) {
            if (!(mask & (1 << bit))) {
                const newMask = mask | (1 << bit);
                if (maskToIndex.has(newMask)) {
                    const key = Math.min(mask, newMask) + "," + Math.max(mask, newMask);
                    if (!processedPairs.has(key)) {
                        processedPairs.add(key);
                        union(i, maskToIndex.get(newMask)[0]);
                    }
                }
            }
        }
        
        // Deleting one letter
        for (let bit = 0; bit < 26; bit++) {
            if (mask & (1 << bit)) {
                const newMask = mask ^ (1 << bit);
                if (maskToIndex.has(newMask)) {
                    const key = Math.min(mask, newMask) + "," + Math.max(mask, newMask);
                    if (!processedPairs.has(key)) {
                        processedPairs.add(key);
                        union(i, maskToIndex.get(newMask)[0]);
                    }
                }
            }
        }
        
        // Replacing one letter
        for (let bit = 0; bit < 26; bit++) {
            if (mask & (1 << bit)) {
                for (let newBit = 0; newBit < 26; newBit++) {
                    if (!(mask & (1 << newBit))) {
                        const newMask = (mask ^ (1 << bit)) | (1 << newBit);
                        if (maskToIndex.has(newMask)) {
                            const key = Math.min(mask, newMask) + "," + Math.max(mask, newMask);
                            if (!processedPairs.has(key)) {
                                processedPairs.add(key);
                                union(i, maskToIndex.get(newMask)[0]);
                            }
                        }
                    }
                }
            }
        }
    }
    
    const groups = new Set();
    let maxGroupSize = 0;
    
    for (let i = 0; i < words.length; i++) {
        const root = find(i);
        groups.add(root);
        maxGroupSize = Math.max(maxGroupSize, size.get(root));
    }
    
    return [groups.size, maxGroupSize];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目