[leetcode] 1202. Smallest String With Swaps

[leetcode] 1202. Smallest String With Swaps

Description

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]Output: "bacd"Explaination: Swap s[0] and s[3], s = "bcad"Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]Output: "abcd"Explaination: Swap s[0] and s[3], s = "bcad"Swap s[0] and s[2], s = "acbd"Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]Output: "abc"Explaination: Swap s[0] and s[1], s = "bca"Swap s[1] and s[2], s = "bac"Swap s[0] and s[1], s = "abc"

Constraints:

1 <= s.length <= 10^5.0 <= pairs.length <= 10^5.0 <= pairs[i][0], pairs[i][1] < s.lengths only contains lower case English letters.

分析

题目的意思是：给你一个数组的pairs，表示字符串能够进行位置交换的操作。这道题的关键点事怎么求解，我也没做出来，看了一下别人的解法，好像是要用到深度优先搜索，首先是构建一个词典d来存储paris的索引，然后再遍历这个字典d，下面的深度优先搜索找最佳的pair，有些地方我看的也不是很懂，希望有人多交流一下哈。

代码

class Solution: def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str: d = defaultdict(list) for a,b in pairs: d[a].append(b) d[b].append(a) def dfs(x,A): if(x in d): A.append(x) for y in d.pop(x): dfs(y,A) s=list(s) while(d): x=next(iter(d)) A=[] dfs(x,A) A=sorted(A) B=sorted([s[i] for i in A]) for i,b in enumerate(B): s[A[i]]=b return ''.join(s)

参考文献

​​[LeetCode] Clean Python DFS | O( n log n )​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。