X

LEETCODE 1202. Smallest String With Swaps 解题思路分析

题目大意:

交换字符串中的元素

给你一个字符串 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 中只含有小写英文字母


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1202

解题思路分析:

这道题核心是要想到使用Union-Find的方式来解题。简单来说就是分组。pairs中的数字对代表可以两两交换的元素,比如第一位和第二位可以交换,第二位和第五位可以交换,继而可得出,第1,2,5这三位之间可以随意交换,这样我们可以将1,2,5位的三个元素由小到大排列即可。因此,问题就转化为,通过pairs找到所有不连通的集合,然后将各个集合升序排列,最后在组合到一起即是结果。

编码思路如下:

  1. 先将字符串分成N组。(N为字符串长度)
  2. 通过pairs找到所有不重合的组。
  3. 将每一组排序
  4. 循环字符串,查看当前位属于哪一组,并输出所属组中最小的元素。

编码时,使用union方法进行分组,root方法查找字符串当前位属于哪一组。利用PriorityQueue为组内元素排序。

看下完整实现代码:

int[] union; // 分组用数组。union[i]表示当前位的根下标(即属于哪一组)。
Map<Integer, PriorityQueue> map = new HashMap<>(); // 记录每组中的元素,并排序
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    int length = s.length(); // 字符串长度
    union = new int[length]; // 初始化分组数组
    for(int i=0;i<length;i++){ // 默认当前字符的根为自己
       union[i]=i; 
    }
    for(List<Integer> pair : pairs){
        // 利用union方法合并组(能连通的部分都归为一组)
        union(pair.get(0),pair.get(1));
    } // 分组完成
    for(int i=0;i<length;i++){ // 循环字符串长度
        int root = root(i); // 查看当前位所属哪一组
        // 从Map中取出保存当前组的Queue。 
        PriorityQueue q = map.getOrDefault(root, new PriorityQueue());
        // 将当前位对应的字符加入到Queue中。
        // 将元素存入PriorityQueue后,会自动排序
        q.offer(s.charAt(i));
        map.put(root, q); // 保存map
    }
    StringBuilder res=new StringBuilder(); // 返回值
    for(int i=0;i<length;i++){
        // 取出当前位所在组中的最小元素,加入返回结果
        res.append(map.get(root(i)).poll());
    }
    return res.toString();
}
// 合并(分组)方法
void union(int index1, int index2){
    // 将index1的根连接到index2的根上
    union[root(index2)] = root(index1);
}
// 查找根的方法。
int root(int i){
    int index = i;
    // 值等于下标的元素都为根
    // 如果值不等于下标,将值付给下标之后继续查找
    while(union[index] != index){
        index=union[index];
    }
    // 更新下标为i的根。(此处跟新为了优化效率)
    union[i]=index;
    return index; // 返回根
}

本算法执行速度为86ms。

Runtime: 86 ms, faster than 42.75% of Java online submissions for Smallest String With Swaps.

Memory Usage: 107.6 MB, less than 100.00% of Java online submissions for Smallest String With Swaps.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1202-smallest-string-with-swaps-解题思路分析/
Categories: leetcode
kwantong: