Medium

题目描述

给你一个字符串 s，以及该字符串中一些字符的索引对数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以任意多次交换在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1：

输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3]，s = "bcad"
交换 s[1] 和 s[2]，s = "bacd"

示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3]，s = "bcad"
交换 s[0] 和 s[2]，s = "acbd"
交换 s[1] 和 s[2]，s = "abcd"

示例 3：

输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1]，s = "bca"
交换 s[1] 和 s[2]，s = "bac"
交换 s[0] 和 s[1]，s = "abc"

提示：

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s 只含有小写英文字母

解题思路

这是一个典型的连通分量问题，可以用图论的思想来解决。

核心思路： 如果两个位置可以通过交换连接起来，那么它们就属于同一个连通分量。在同一个连通分量内的所有字符都可以通过一系列交换操作重新排列。为了得到字典序最小的字符串，我们需要将每个连通分量内的字符按升序排列。

解法选择：

  1. 并查集（Union-Find）：最适合处理动态连通性问题，推荐解法
  2. DFS/BFS：构建图后遍历连通分量，实现相对复杂
  3. 图的邻接表：需要额外的图构建过程

算法步骤（并查集）：

  1. 初始化并查集，将所有可交换的位置对进行合并
  2. 遍历字符串，将属于同一连通分量的字符收集起来
  3. 对每个连通分量的字符进行排序
  4. 按照原始位置顺序，将排序后的字符重新分配到结果字符串中

时间复杂度： O(n·α(n) + m·α(n) + k·log k)，其中 n 是字符串长度，m 是 pairs 数量，k 是最大连通分量的大小，α(n) 是阿克曼函数的反函数。 空间复杂度： O(n)，主要用于并查集和临时存储。

代码实现

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.length();
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) -> int {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        for (auto& pair : pairs) {
            int rootA = find(pair[0]);
            int rootB = find(pair[1]);
            if (rootA != rootB) {
                parent[rootA] = rootB;
            }
        }
        
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            groups[find(i)].push_back(i);
        }
        
        string result = s;
        for (auto& [root, indices] : groups) {
            string chars;
            for (int idx : indices) {
                chars += s[idx];
            }
            sort(chars.begin(), chars.end());
            sort(indices.begin(), indices.end());
            
            for (int i = 0; i < indices.size(); i++) {
                result[indices[i]] = chars[i];
            }
        }
        
        return result;
    }
};

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        for a, b in pairs:
            root_a, root_b = find(a), find(b)
            if root_a != root_b:
                parent[root_a] = root_b
        
        groups = {}
        for i in range(n):
            root = find(i)
            if root not in groups:
                groups[root] = []
            groups[root].append(i)
        
        result = list(s)
        for indices in groups.values():
            chars = [s[i] for i in indices]
            chars.sort()
            indices.sort()
            
            for i, idx in enumerate(indices):
                result[idx] = chars[i]
        
        return ''.join(result)

public class Solution {
    public string SmallestStringWithSwaps(string s, IList<IList<int>> pairs) {
        int n = s.Length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        foreach (var pair in pairs) {
            int rootA = Find(pair[0]);
            int rootB = Find(pair[1]);
            if (rootA != rootB) {
                parent[rootA] = rootB;
            }
        }
        
        var groups = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            int root = Find(i);
            if (!groups.ContainsKey(root)) {
                groups[root] = new List<int>();
            }
            groups[root].Add(i);
        }
        
        char[] result = s.ToCharArray();
        foreach (var indices in groups.Values) {
            var chars = indices.Select(i => s[i]).OrderBy(c => c).ToArray();
            indices.Sort();
            
            for (int i = 0; i < indices.Count; i++) {
                result[indices[i]] = chars[i];
            }
        }
        
        return new string(result);
    }
}

var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    for (const [a, b] of pairs) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA !== rootB) {
            parent[rootA] = rootB;
        }
    }
    
    const groups = new Map();
    for (let i = 0; i < n; i++) {
        const root = find(i);
        if (!groups.has(root)) {
            groups.set(root, []);
        }
        groups.get(root).push(i);
    }
    
    const result = s.split('');
    for (const indices of groups.values()) {
        const chars = indices.map(i => s[i]).sort();
        indices.sort((a, b) => a - b);
        
        for (let i = 0; i < indices.length; i++) {
            result[indices[i]] = chars[i];
        }
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n·α(n) + m·α(n) + k·log k)
空间复杂度O(n)

其中 n 是字符串长度，m 是 pairs 数量，k 是最大连通分量的大小，α(n) 是阿克曼函数的反函数（实际中可视为常数）。

相关题目